本帖最後由 許婷芳 於 2020-8-15 17:50 編輯
利用深度優先搜尋演算法 (Depth-First-Search, DFS)，找出樹狀結構中，自根部開始最深的距離。
輸入分為兩部分，第一部分為共有幾個成員，第二部分為所有關係。
以下圖為例，共有6個成員，它們的關係是 2-1-0-3-5-4。
輸出顯示最深距離。
 - import java.util.Scanner;
- public class P4 {
- Scanner s;
- int n; //成員數
- int rlts[][]; //所有關係
- int hasParent[]; //每個成員各有幾個父母
- int hasChild[]; //每個成員各有幾個孩子
- int theHead=0; //最老的祖先
- int dfsResult;
- P4()
- {
- s=new Scanner(System.in);
- n=s.nextInt();
- rlts=new int[n-1][2];
- for(int i=0; i<n-1; i++)
- for(int j=0; j<2; j++)
- rlts[i][j]=s.nextInt();
- hasParent=new int[n];
- hasChild=new int[n];
- for(int i=0; i<n; i++)
- hasParent[i]=0;
- for(int i=0; i<n; i++)
- hasChild[i]=0;
- for(int i=0; i<n-1; i++) //計算每個成員，父母及孩子的數量
- {
- hasChild[rlts[i][0]]++;
- hasParent[rlts[i][1]]++;
- }
- /*
- 2 1
- 1 0
- 0 3
- 3 5
- 5 4
- hasChild 1,1,1,1,0,1
- hasParent 1,1,0,1,1,1
- */
- for(int i=0; i<n; i++)
- if(hasParent[i]==0) //誰沒父母，就是最老的祖先
- theHead=i;
- dfsResult=dfs(theHead);
- System.out.println("最深距離: "+dfsResult);
- }
- int dfs(int h) //深度優先搜尋，回傳最遠距離
- {
- if(hasChild[h]==0) //無孩子，表示已到尾端
- return 0;
- else
- {
- for(int i=0; i<n-1; i++) //找他的小孩是誰
- if(rlts[i][0]==h)
- return dfs(rlts[i][1])+1; //將孩子變成父母丟回去遞迴，距離值加1
- }
- return 0; //回傳0避免編譯錯誤
- }
- /*
- dfs(2)
- =dfs(1)+1
- =dfs(0)+1+1
- =dfs(3)+1+1+1
- =dfs(5)+1+1+1+1
- =dfs(4)+1+1+1+1+1
- =0+1+1+1+1+1
- =5
- */
- public static void main(String[] args) {
- new P4();
- }
- }
|
