種子論壇 | 高雄市資訊培育協會學員討論區

標題: 樹狀圖 (一) - 無分岔點 [打印本頁]

作者: 李泳霖 時間: 2023-4-9 09:32 標題: 樹狀圖 (一) - 無分岔點

本帖最後由李泳霖於 2023-6-4 14:34 編輯

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

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

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

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

範例輸入

6
0 3
1 0
5 4
2 1
3 5

範例輸出

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

作者: 東緯 時間: 2023-5-28 17:05

此帖僅作者可見

作者: 李泳霖 時間: 2023-6-4 14:34

此帖僅作者可見

作者: 東緯 時間: 2023-6-4 15:01

此帖僅作者可見

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