目錄
重要觀念整理
1. 資料結構選擇
| 演算法 | 資料結構 | 原因 |
|---|---|---|
| DFS | 遞迴 / Stack | 需要回溯到上一層節點 |
| BFS | Queue | 需要按層級順序處理 |
2. 節點類型判斷
if parent[id] == -1:
# 根節點：沒有父節點
types = "root"
elif len(tree[id]) > 0:
# 內部節點：有子節點
types = "internal node"
else:
# 葉節點：沒有子節點
types = "leaf"3. 深度與高度的計算
-
深度 (Depth)：從根節點往下傳遞，每往下一層 +1
dfs(Tree, next_node, depth + 1) -
高度 (Height)：從葉節點往上回傳，取子節點中的最大值
height = max(dfs(Tree, next_node, depth + 1), height)
4. defaultdict 的使用
from collections import defaultdict
tree = defaultdict(list)好處：
-
自動初始化不存在的 key 為空 list
-
不需要檢查 key 是否存在就可以直接 append
時間複雜度分析
| 操作 | 時間複雜度 | 說明 |
|---|---|---|
| DFS 遍歷 | O(V + E) | 每個節點和邊都訪問一次 |
| BFS 遍歷 | O(V + E) | 每個節點和邊都訪問一次 |
| 計算深度/高度 | O(V + E) | 使用 DFS 遍歷一次 |
其中 V 是節點數，E 是邊數。對於樹來說，E = V - 1。
常見應用
DFS 適用場景
-
路徑搜尋
-
拓撲排序
-
偵測循環
-
計算連通分量
BFS 適用場景
-
最短路徑（無權重圖）
-
層級遍歷
-
找到距離某節點最近的節點