← All notes
LeetCode Cycle 10：圖 BFS / DFS、拓撲排序、Union-Find
樹是「沒有環的圖」——把樹的搜索套到圖上會無窮迴圈。Cycle 10 後半把命題從「樹好搜」進階到「圖怎麼搜」：visited set 為什麼必要、有向圖環怎麼測（三色 DFS）、拓撲排序兩種寫法、Union-Find 為什麼能 O(α(n)) 近似常數。內部使用。
Tree → Graph 的本質差別只有一條：graph 可以有 cycle[^1][^2]。Cycle 帶來的後果：
- 必須 visited set——否則 DFS 進入環會無限遞迴、爆 stack
- 必須區分有向 / 無向——cycle detection 寫法不同
- 依賴排序問題只在 DAG（有向無環圖）成立——這引出 topological sort[^3]
- 連通性問題 有時 BFS / DFS 不夠快，要 UnionFind 才能 O(α(n))
面試 graph 題的判定就在「選哪個工具」。下面把這 4 個工具的取捨拆透。