Board logo

標題: 樹狀圖 (一) - 無分岔點 [打印本頁]
作者: 李泳霖    時間: 2023-7-7 22:10     標題: 樹狀圖 (一) - 無分岔點

本帖最後由 李泳霖 於 2023-7-15 16:51 編輯

樹狀圖分析的其中一種方法為 深度優先搜尋演算法 (DFS)，我們可利用此演算法來找出樹狀結構中，節點間的關係以及自根部開始最深的距離。

但在程式競賽或APCS檢定中若遇到類似的題目，老師並不建議使用 DFS 來解題。原因是 DFS 為遞迴的結構，遞迴結構在對效率極度要求的程式競賽或APCS檢定中，非常容易發生 StackOverFlowError、TLE、MLE 等疑難雜症。

因此對於樹狀圖分析這類的考題，老師會帶同學們以從葉節點往根節點走訪的思維來解題。當然，依然會提供 DFS 解法的程式碼給同學們參考。

下面的這個例子為一無分岔點的樹狀圖，輸入分為兩部分，第一部分為共有幾個成員，第二部分為所有關係。請同學們試著找出在這樣的一個樹狀結構中，根節點是誰、葉節點是誰、最深的距離是多少？

範例輸入

6
0 3
1 0
5 4
2 1
3 5

範例輸出

根節點: 2
葉節點: 4
最深距離: 5



  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;

  5. public class Ch01
  6. {
  7.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
  8.         String raw[];
  9.         int n;//節點數
  10.         Node root,leaf;//根節點,葉節點
  11.         Node node[];
  12.       
  13.         Ch01() throws NumberFormatException, IOException//建構子(初始化)
  14.         {
  15.                 n=Integer.parseInt(br.readLine());//輸入節點並存入整數n
  16.                 node=new Node[n];//建立n張設計圖，用以記錄每個點的父&子&距離
  17.                
  18.                 for(int i=0;i<n;i++)
  19.                         node[i]=new Node();//建立物件，將每個節點實體化(含父&子&距離)
  20.                
  21.                 for(int i=0;i<n-1;i++)//共有n-1行(個關係)每行有父&子
  22.                 {
  23.                         raw=br.readLine().split(" ");
  24.                         int p=Integer.parseInt(raw[0]);
  25.                         int c=Integer.parseInt(raw[1]);
  26.                         node[c].parent=p;
  27.                         node[p].child=c;
  28.                 }
  29.                
  30.                 for(int i=0;i<n;i++)
  31.                 {
  32.                         if(node[i].parent==-1)//沒有爸爸
  33.                                 root=node[i];
  34.                         if(node[i].child==-1)//沒有小孩
  35.                                 leaf=node[i];
  36.                 }
  37.                
  38.         }
  39.         public static void main(String[] args) throws NumberFormatException, IOException
  40.         {
  41.                 new Ch01();//建立並呼叫建構子
  42.         }
  43. }
  44. class Node
  45. {
  46.         int parent=-1,child=-1;//每個點的父&子
  47.         int h=0;//每個點的最深距離
  48. }
複製代碼
作者: 張博翔    時間: 2023-7-8 17:30

此帖僅作者可見
作者: 江家同    時間: 2023-7-8 17:30

此帖僅作者可見
作者: 黃昱齊    時間: 2023-7-8 17:30

此帖僅作者可見
作者: 歐睿仁    時間: 2023-7-8 17:30

此帖僅作者可見
作者: 王競儀    時間: 2023-7-8 17:31

此帖僅作者可見
作者: 李泳霖    時間: 2023-7-15 16:50

此帖僅作者可見
作者: 黃昱齊    時間: 2023-7-15 17:29

此帖僅作者可見
作者: 江家同    時間: 2023-7-15 17:29

此帖僅作者可見
作者: 歐睿仁    時間: 2023-7-15 17:30

此帖僅作者可見
作者: 秉宏1    時間: 2023-7-15 17:32

此帖僅作者可見



歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/) Powered by Discuz! 7.2