第9章 圖演算法#

本章目標#

• 實作 DFS 與 BFS，理解兩者在圖上的行為差異與應用。
• 掌握 Dijkstra 與 Bellman-Ford 兩種最短路徑演算法。
• 實作 Kruskal 與 Prim 兩種最小生成樹演算法。

章前言#

有了第7章的圖表示法與堆積、併查集，本章終於可以解決「圖上的經典問題」——這也是本書前八章所有零件的大會師：BFS 用到佇列、DFS 用到堆疊、Dijkstra 用到優先權佇列、Kruskal 用到排序與併查集。

三類問題：

1. 走訪：把圖上每個點都摸一遍。DFS 沿一條路走到底再回頭，適合找環、拓撲排序、迷宮解路；BFS 一層層擴散，在無權圖中天然求出最短路徑（步數最少），也用於層級分析與連通分量。
2. 最短路徑：帶權圖上找「最便宜的路」。Dijkstra 適合邊權非負的圖，用貪心策略配合堆積，O((V+E) log V)；Bellman-Ford 允許負權邊（如匯率套利、折扣），放鬆所有邊 V−1 輪，O(V·E)，還能偵測負環。
3. 最小生成樹（MST）：用最少的總邊權把所有點連起來（如布線、鋪水管）。Kruskal 按邊權從小到大貪心選邊、用併查集擋掉成環的邊；Prim 從一個點出發、用堆積不斷「長出」最近的下一個點。兩者都基於切割性質：橫跨任一切割的最輕邊必屬於某棵 MST。

學完本章，你應該能對著任何一張「地圖」，回答「哪裡到哪裡最快」「怎麼把所有人連起來最省錢」這類問題。