深度優先搜尋演算法 (一) - 無分岔點最深距離

許婷芳

利用深度優先搜尋演算法 (Depth-First-Search, DFS)，找出樹狀結構中，自根部開始最深的距離。

輸入分為兩部分，第一部分為共有幾個成員，第二部分為所有關係。
以下圖為例，共有6個成員，它們的關係是 2-1-0-3-5-4。

輸出顯示最深距離。

1. import java.util.Scanner;
   
2. 
   
3. public class P4 {
   
4. 
   
5.         Scanner s;
   
6.         int n;              //成員數
   
7.         int rlts[][];       //所有關係
   
8.         int hasParent[];    //每個成員各有幾個父母
   
9.         int hasChild[];     //每個成員各有幾個孩子
   
10.         int theHead=0;      //最老的祖先
    
11.         int dfsResult;
    
12. 
    
13.         P4()
    
14.         {
    
15.                 s=new Scanner(System.in);
    
16.                 n=s.nextInt();
    
17.                 rlts=new int[n-1][2];
    
18.                 for(int i=0; i<n-1; i++)
    
19.                         for(int j=0; j<2; j++)
    
20.                                 rlts[i][j]=s.nextInt();
    
21.                 hasParent=new int[n];
    
22.                 hasChild=new int[n];
    
23. 
    
24.                 for(int i=0; i<n; i++)
    
25.                         hasParent[i]=0;
    
26.                 for(int i=0; i<n; i++)
    
27.                         hasChild[i]=0;
    
28.                 for(int i=0; i<n-1; i++)   //計算每個成員，父母及孩子的數量
    
29.                 {
    
30.                         hasChild[rlts[i][0]]++;
    
31.                         hasParent[rlts[i][1]]++;
    
32.                 }
    
33.                 /*
    
34.                   2 1
    
35.                   1 0
    
36.                   0 3
    
37.                   3 5
    
38.                   5 4         
    
39.                  hasChild 1,1,1,1,0,1              
    
40.                  hasParent 1,1,0,1,1,1     
    
41.                  */
    
42.                 for(int i=0; i<n; i++)
    
43.                         if(hasParent[i]==0)   //誰沒父母，就是最老的祖先
    
44.                                 theHead=i;
    
45. 
    
46.                 dfsResult=dfs(theHead);
    
47. 
    
48.                 System.out.println("最深距離: "+dfsResult);
    
49.         }
    
50. 
    
51.         int dfs(int h)     //深度優先搜尋，回傳最遠距離
    
52.         {
    
53. 
    
54.                 if(hasChild[h]==0)     //無孩子，表示已到尾端
    
55.                         return 0;
    
56.                 else
    
57.                 {
    
58.                         for(int i=0; i<n-1; i++)    //找他的小孩是誰
    
59.                                 if(rlts[i][0]==h)
    
60.                                         return dfs(rlts[i][1])+1;   //將孩子變成父母丟回去遞迴，距離值加1
    
61.                 }
    
62.                 return 0;   //回傳0避免編譯錯誤
    
63.         }
    
64. 
    
65.         /*
    
66.              dfs(2)
    
67.              =dfs(1)+1
    
68.              =dfs(0)+1+1
    
69.              =dfs(3)+1+1+1
    
70.              =dfs(5)+1+1+1+1
    
71.              =dfs(4)+1+1+1+1+1
    
72.              =0+1+1+1+1+1
    
73.              =5
    
74.          */
    
75. 
    
76.         public static void main(String[] args) {
    
77.                 new P4();
    
78.         }   
    
79. }

複製代碼