圖與圖演算法

📌 本頁使用方式（cppds Ch.9｜講義 08）

① 照節次讀：每一節先讀說明、動手玩互動元件，預測結果再按按鈕驗證。 ② 對照講義：頁上 §徽章對應 cppds 章節；細節與完整程式請回講義 08 與 cppds 原文。 ③ 每節做 quiz：答錯就回到該節重讀，不要往下跳。 ④ 最後翻關鍵詞彙卡（29 張）自測術語（中文為主、術語附英文），並用 REF 總覽區當速查表。標「官方選讀」的節屬 cppds 正文，但課程第一輪可略過。

📑 講義 08 PDF 🖥 講義 08 HTML 📖 cppds 原文（Graphs）📘 Hello 演算法（圖）🏠 章節總覽

CONTENTS · 內容目錄

P00引言：圖的術語 P01圖的表示方法 P02廣度優先搜尋 BFS P03Word Ladder P04深度優先搜尋 DFS P05騎士巡邏 Knight's Tour P06Dijkstra 最短路徑 P07Prim 最小生成樹 P08拓撲排序（官方選讀） P09強連通元件（官方選讀） EX練習題 REF總覽比較表 QUIZ自我檢測（6 題） CARD關鍵詞彙卡（29 張）

PROLOGUE · 開場

圖是什麼？先把術語都講清楚 cppds §9.1–9.2

圖（graph）可以用來描述許多現實世界的關係：道路系統、航班、網際網路連線、課程先修關係等等。一旦我們把問題用圖表示出來，就可以套用標準的圖演算法解決原本看似困難的問題！

三個核心元素 頂點（Vertex / Node）：圖的基本單位，有一個 key（名稱），可選擇性地附帶 value 或 payload。
邊（Edge / Arc）：連接兩個頂點，表示兩者之間有關係。邊可以是單向（有向圖 digraph）或雙向。
權重（Weight）：邊上可附加成本，例如兩城市間的距離、網路延遲等。

形式上我們把圖寫成 $G = (V, E)$：$V$ 是頂點集合，$E$ 是邊的集合。每條邊是一個 tuple $(v, w)$，其中 $v, w \in V$；如果有權重就寫成 $(v, w, c)$。

路徑、循環、樹、DAG

術語對照

|V|6

|E|9

類型有向加權

關鍵概念

Path 由邊串聯的頂點序列 $w_1, w_2, \ldots, w_n$，每個相鄰對 $(w_i, w_{i+1}) \in E$。

Cycle 起點＝終點的 path 。

DAG Directed Acyclic Graph：沒有 cycle 的有向圖；可解決許多排程／依賴問題。

Tree 連通且無 cycle 的圖；下一章專題討論。

頂點的三色狀態（後續演算法都會用到）

BFS 與 DFS 都會用「白／灰／黑」三色追蹤每個頂點被造訪的程度。請先記住這套語義，後續每一節都會直接套用：

White：尚未發現 Gray：已發現、尚未完成 Black：已完全探索 Current：目前處理中 Start：起點原始邊樹邊（搜尋樹）正在檢查

每一節版面都採用左「圖視覺化＋控制列」、右「即時統計＋虛擬碼＋複雜度」的形式。請按 ▶ 開始跑完整動畫，或按 → 單步一步一步觀察。

PART 01 · 圖的表示

怎麼把圖塞進電腦？相鄰矩陣 vs 相鄰串列 cppds §9.3–9.6

本課程的 Graph 以 setVertex(key)、addEdge(u, v, w) 建圖，並透過公開的 vertices map 查詢與迭代。setVertex 對既有 key 是 no-op，不會清掉原有 edges 或 traversal state；vertices.count(key) 檢查頂點是否存在。

相鄰矩陣
Adjacency Matrix

相鄰串列
Adjacency List

點選頂點：

何時用矩陣？

適合稠密圖（dense，邊數接近 $|V|^2$）。
✅ 直接 $O(1)$ 查詢任兩點是否相連
❌ 空間 $O(|V|^2)$
❌ 對稀疏圖極度浪費

空間$O(|V|^2)$

查邊$O(1)$

列鄰居$O(|V|)$

何時用串列？

適合稀疏圖（sparse，邊數遠小於 $|V|^2$）。
✅ 空間 $O(|V|+|E|)$
✅ 列出鄰居只需 $O(\deg(v))$
❌ 查特定邊需走過鄰居清單

空間$O(|V|+|E|)$

查邊（std::map）$O(\log\deg(v))$

列鄰居$O(\deg(v))$

真實世界：稀疏為主

以 Word Ladder 為例：5,110 個字的矩陣有 26,112,100 格；實作儲存 53,286 條有向 adjacency entries（26,643 組無向單字對），約占 0.20%。

C++ 實作：Vertex 與 Graph 類別 pythonds3/cppds/graph.hpp

每個 Vertex 用 map 紀錄它的鄰居及邊權重；Graph 再用一個 map 把 key 對應到 Vertex 物件：

class Vertex {
  public:
    string key;
    map<string, int> neighbors;   // 鄰居 key → 權重
    string color = "white";
    Vertex(string k) { key = k; }
};
 
class Graph {
  public:
    map<string, Vertex> vertices;
    void setVertex(string key) { if (vertices.count(key) == 0) vertices.emplace(key, Vertex(key)); }
    void addEdge(string fromVert, string toVert, int weight = 0) {
        if (vertices.count(fromVert) == 0) setVertex(fromVert);
        if (vertices.count(toVert) == 0) setVertex(toVert);
        vertices[fromVert].neighbors[toVert] = weight;
    }
};

小提醒本章後續所有演算法（BFS/DFS/Dijkstra/Prim）都建立在相鄰串列實作之上。Vertex 類別在不同節中會擴充不同欄位（如 color, distance, previous, discovery_time, closing_time），但底層結構不變。

講義完整範例：Graph 類別的使用畫面

講義 08 · 建頂點、加邊、走訪相鄰串列

#include <iostream>
#include "pythonds3/cppds/graph.hpp"   // Vertex + Graph（上面的完整列表）
using namespace std;
 
int main() {
    Graph g;
    g.addEdge("0","1",5); g.addEdge("0","5",2); g.addEdge("1","2",4);
    g.addEdge("2","3",9); g.addEdge("3","4",7); g.addEdge("3","5",3);
    g.addEdge("4","0",1); g.addEdge("5","4",8); g.addEdge("5","2",1);
 
    for (auto& p : g.vertices)
        for (auto& n : p.second.neighbors)
            cout << "(" << p.first << "," << n.first << "," << n.second << ") ";
    cout << endl;
    return 0;
}
 

預期輸出

(0,1,5) (0,5,2) (1,2,4) (2,3,9) (3,4,7) (3,5,3) (4,0,1) (5,2,1) (5,4,8)

每組 (from, to, weight) 對應一條有向邊，addEdge 會補上不存在的頂點。ordered map 查頂點為 O(log |V|)、查特定鄰邊為 O(log deg(v))。

PART 02 · 廣度優先搜尋

BFS：一層一層往外擴散 cppds §9.9–9.10

給定起點 $s$，廣度優先搜尋（Breadth-First Search）會找出圖中所有從 $s$ 可達的頂點。它最迷人的性質是：會先找到所有距離 $s$ 為 $k$ 的頂點，才開始找距離 $k+1$ 的。換句話說，BFS 自動產生「最少邊數路徑」（在無權圖上就是最短路徑）。

核心資料結構 BFS 用 Queue（先進先出）決定下一個頂點。每次執行前先把所有頂點重設為 white、distance = INT_MAX（尚不可達）、空 previous；起點在 enqueue 前設為 gray 與 distance 0，避免被鄰居重複加入。

起點速度

          Queue：
          empty
        

即時統計 LIVE

已探索

當前距離

—

頂點狀態表

虛擬碼 CODE

#include "pythonds3/cppds/graph.hpp"
#include <climits>
#include <queue>
#include <stdexcept>
void bfsPanel(Graph& g, const string& startKey) {
    if (!g.vertices.count(startKey)) { throw invalid_argument("missing start"); } for (auto& [key, v] : g.vertices) { v.color="white"; v.distance=INT_MAX; v.previous=""; }
    Vertex& start = g.vertices.at(startKey); start.distance = 0;
    start.color = "gray";
    queue<string> pending;
    pending.push(startKey);
    while (!pending.empty()) {
        string currentKey = pending.front(); pending.pop();
        Vertex& current = g.vertices.at(currentKey); for (auto& [neighborKey, weight] : current.neighbors) {
            Vertex& neighbor = g.vertices.at(neighborKey); if (neighbor.color == "white") {
                neighbor.color = "gray";
                neighbor.distance = current.distance + 1;
                neighbor.previous = currentKey;
                pending.push(neighborKey);
            } } current.color = "black"; } }

複雜度

時間$O(\lvert V\rvert + \lvert E\rvert)$

空間$O(\lvert V\rvert)$

最短路徑無權圖 ✓

為什麼是 $O(|V|+|E|)$？外層 while 每個頂點最多進 queue 一次（白色才會被加），所以是 $O(|V|)$。內層 for 走每個被 dequeue 出來的點的所有鄰居，整體加總就是每條邊被檢查一次，也就是 $O(|E|)$。兩者相加：$O(|V|+|E|)$。

BFS 的兩個重要性質 (1) 最短路徑樹：沿著 previous 指標往回走，可以重建從任何可達頂點回到起點的最少邊數路徑。
(2) 一次解多個問題：一次 BFS 同時得到起點到「所有可達頂點」的最短距離，不需要重新跑 $|V|$ 次！

範例：在真實地圖上跑 BFS Google Maps Explained（secretsofmaps.com） 把本節的 BFS 搬到真實道路網上：地圖上左鍵點起點、右鍵點終點（或按 Select 2 Random Points），再按播放，就能看到 BFS 像水面漣漪一樣一圈一圈往外擴散，直到碰到終點。網站的頂點是 OpenStreetMap 的路口、邊是路段，資料透過 Overpass API 即時抓取，和本頁的 Graph／Vertex 是同一套抽象。
建議玩法：先跑 BFS，觀察它如何逐層搜尋，而不優先朝終點前進；接著依序解鎖 DFS（一頭鑽進去、找到的不一定最短）、Greedy（只看離終點多遠，遇到河就繞遠路）、A*（同時考慮已走成本與到終點的估計成本）、Bidirectional BFS／A*（從起點與終點兩側搜尋，實際縮減幅度依路網與位置而異）、最後的 A* + 查表（觀察預先整理路網資訊如何減少查詢工作）。 看完再回頭讀 PART 06：A* 在已走成本上加入到終點的啟發式估計，決定搜尋優先順序。 路段距離不同時，BFS 找到的最少邊數不一定是最短路程；這裡先比較搜尋方式。
小提醒：介面為英文；地圖資料第一次載入可能要一、兩分鐘，Overpass 偶爾會限流，請稍等再試；廣告阻擋器可能讓地圖載不出來。演算法預設隨導覽角色 Geo 的對話逐一解鎖，想直接玩可按 Unlock All Algorithms。作者 Adam Kulikowski，改作自 honzaap/Pathfinding，MIT 授權；原始碼。

講義完整範例：Word Ladder 的實際執行

講義 08 · bfs + traverse：從 fool 爬到 sage

#include <iostream>
#include "pythonds3/cppds/graph_algos.hpp"   // buildGraph + bfs + traverse
using namespace std;
 
int main() {
    Graph g = buildGraph({"fool", "cool", "pool", "poll", "pole",
                         "pall", "fall", "fail", "foil", "foul",
                         "pope", "pale", "sale", "sage", "page"});
    bfs(g, "fool");
    traverse(g, "sage");                 // 沿 previous 指標回溯
    for (auto& p : g.vertices)           // 單字（與 fool 的距離）
        cout << p.first << "(" << p.second.distance << ") ";
    cout << endl;
    return 0;
}
 

實際執行

sage->page->pale->pall->poll->pool->fool
cool(1) fail(2) fall(3) foil(1) fool(0) foul(1) page(5) pale(4) pall(3) pole(3) poll(2) pool(1) pope(4) sage(6) sale(5)

traverse 印 previous 鏈，任何可達單字回溯到 fool 都是最短路。

PART 03 · Word Ladder

Word Ladder：把 BFS 應用到「換字謎題」 cppds §9.7–9.8

Word Ladder：把一個單字一次改一個字母變成另一個單字，每一步都必須是有效單字。經典題目：FOOL → SAGE，最少要幾步？

FOOL → POOL → POLL → POLE → PALE → SALE → SAGE

把每個單字當頂點、把「只差一個字母」的單字對連邊，問題就變成「在這張圖上找最短路徑」，正是 BFS 的拿手好戲！

建圖技巧：bucket 法（避免 $O(n^2)$ 比對）

若有 $n=5{,}110$ 個四字母單字，兩兩比對需要約 $\binom{n}{2} \approx 1.3 \times 10^7$ 次，太慢。聰明的做法：用 bucket 標籤，將每個字母位置依次替換成底線 _，把所有共用同一個 bucket 的單字連起來。

Bucket 構造範例 POPE、POPS 都會落入 bucket POP_；
FOOL、POOL、COOL、TOOL 都落入 bucket _OOL。
每個 bucket 內部的所有單字兩兩相連 → 所有「只差一個字母」的單字對都被連上了！

起點終點

速度

          Queue：
          empty
        

最短路徑

—

步數—

建圖統計

|V|15

|E|—

已探索0

演算法複雜度

建圖（bucket）$O(n \cdot L)$

BFS$O(\lvert V\rvert + \lvert E\rvert)$

$n$ = 字數, $L$ = 字長

單字集合：fool, cool, pool, poll, pole, pall, fall, fail, foil, foul, pope, pale, sale, sage, page。圖中只畫出 bucket 法產生的邊（同 bucket 內兩兩相連）；BFS 從起點往外擴散時會以橘色標記正在處理的頂點，綠色表示已被加入搜尋樹。

PART 04 · 深度優先搜尋

DFS：一條路走到黑，碰壁再回頭 cppds §9.15–9.16

BFS 一層一層擴散，深度優先搜尋（Depth-First Search）則是沿一條分支盡可能往深走，走不下去才回退（backtrack）到上一個還有未探索鄰居的頂點。BFS 用 queue，DFS 自然用遞迴（隱式 stack）。

DFS 的兩個新欄位除了 color 與 previous，DFS 還記錄：
discovery_time（發現時間）：頂點從 white 變 gray 的時間步。
closing_time（結束時間）：頂點從 gray 變 black 的時間步。
這兩個時間滿足括號性質（parenthesis property）：每個子節點的 [discovery, closing] 區間都完全嵌套在父節點的區間內。

起點速度

          Recursion stack（隱式）：
          empty
        

          時間計數：
          0
        

頂點時間表

虛擬碼 CODE

#include "pythonds3/cppds/graph_algos.hpp"
void dfsVisitPanel(DFSGraph&, const string&);
void dfsPanel(DFSGraph& graph) {
    for (auto& [key, v] : graph.vertices) { v.color="white"; v.previous=""; }
    graph.time = 0; graph.discovery.clear(); graph.closing.clear();
    for (auto& [key, v] : graph.vertices) {
        if (v.color == "white") {
            dfsVisitPanel(graph, key);
        } } }
void dfsVisitPanel(DFSGraph& graph, const string& uKey) {
    graph.vertices.at(uKey).color = "gray";
    graph.discovery[uKey] = ++graph.time;
    for (auto& [neighborKey, weight] : graph.vertices.at(uKey).neighbors) {
        if (graph.vertices.at(neighborKey).color == "white") {
            graph.vertices.at(neighborKey).previous = uKey;
            dfsVisitPanel(graph, neighborKey);
        } } graph.vertices.at(uKey).color = "black";
    graph.closing[uKey] = ++graph.time; }

複雜度

時間$O(\lvert V\rvert + \lvert E\rvert)$

空間$O(\lvert V\rvert)$ 遞迴

為什麼要走訪所有頂點？(line 4) 從單一起點 DFS 可能無法走遍整張圖（特別是有向圖或不連通圖）。外層 for v : graph 確保每個白色頂點都會啟動一次 dfsVisit，最終得到一片深度優先森林（DF forest）。

BFS vs DFS 的程式碼對照 DFS 與 BFS 的程式碼幾乎一模一樣，差別只在內層迴圈最後一行：
BFS：queue.enqueue(neighbor)：先把鄰居塞 queue，等以後處理。
DFS：dfsVisit(neighbor)：立刻遞迴下去處理鄰居。
這個小差異就決定了「廣度優先 vs 深度優先」的搜尋順序！

講義 08 · DFSGraph：discovery / closing time 全表

#include <iostream>
#include "pythonds3/cppds/graph_algos.hpp"   // DFSGraph（上面的完整列表）
using namespace std;
 
int main() {
    DFSGraph g;
    g.addEdge("A", "B");  g.addEdge("B", "C");
    g.addEdge("A", "D");  g.addEdge("B", "D");
    g.addEdge("D", "E");  g.addEdge("E", "B");
    g.addEdge("E", "F");  g.addEdge("F", "C");
    g.dfs();
    printf("%4s|%9s|%8s|%9s\n", "Key", "Discover", "Closing", "Previous");
    for (auto& p : g.vertices)
        printf("%4s|%9d|%8d|%9s\n", p.first.c_str(),
               g.discovery[p.first], g.closing[p.first], p.second.previous.c_str());
    return 0;
}
 

預期輸出

 Key| Discover| Closing| Previous
   A|        1|      12|         
   B|        2|      11|        A
   C|        3|       4|        B
   D|        5|      10|        B
   E|        6|       9|        D
   F|        7|       8|        E

對照括號性質：C 的 [3,4] 完全包在 B 的 [2,11] 裡（C 是 B 的子孫）；每個頂點的區間要嘛互相包住、要嘛完全分開，絕不交錯。E→B 那條邊指向還是灰色的祖先，是一條 back edge：它宣告圖裡有循環。

PART 05 · 騎士巡邏

Knight's Tour：DFS + Warnsdorff 啟發式 cppds §9.11–9.14

騎士巡邏：在 $n \times n$ 棋盤上，騎士能否走 $n^2 - 1$ 步、恰好造訪每格一次？這是 DFS 的經典應用：把每格當頂點、把合法走法當邊，問題變成「找出長度為 $n^2 - 1$ 的簡單路徑」。

在 $8\times8$ 棋盤上，adjacency map 儲存 336 條有向 adjacency arcs；每個合法移動的無向關係會以兩個方向儲存，所以等價於 168 條無向邊。

指數爆炸在 $8 \times 8$ 棋盤上，平均分支因子 $k = 5.25$，搜尋樹約有 $5.25^{64} \approx 1.2 \times 10^{46}$ 個節點！純 DFS 在 8x8 棋盤上會跑數分鐘到永遠跑不完。但只要加上一個簡單的啟發式排序，速度可以快上千萬倍。

Warnsdorff 啟發式 下一步永遠選「可走鄰居最少」的格子。

大小起點速度

即時統計 LIVE

已走步數

回退次數

總探索節點0

結果—

虛擬碼 CODE

#include "pythonds3/cppds/graph_algos.hpp"
bool knightTourPanel(int n, vector<string>& path, const string& uKey, int limit, Graph& g) {
    g.vertices.at(uKey).color = "gray";
    path.push_back(uKey);
    if (n >= limit) return true;
    for (const string& neighborKey : orderByAvail(g, uKey)) {
        if (g.vertices.at(neighborKey).color == "white" &&
            knightTourPanel(n + 1, path, neighborKey, limit, g)) return true;
    }
    path.pop_back(); g.vertices.at(uKey).color = "white";
    return false;
}

複雜度

純 DFS$O(k^N)$

Warnsdorff啟發式；最壞仍指數

$N=n^2$, $k$≈分支因子

為什麼選「鄰居最少」而不是「最多」？若每次選鄰居最多的格子，騎士會傾向往中間擠（中間格鄰居多）。一旦中間都用完，四角的孤立格子就再也走不到。反過來「先解決鄰居最少的」，等於先掃完邊角這些「燙手山芋」，中間格子鄰居多、機動性高，留到後段當跳板使用：這就是 Warnsdorff 規則奏效的根本原因。

PART 06 · Dijkstra 最短路徑

Dijkstra：加權圖上的「貪婪式 BFS」 cppds §9.19–9.21

Dijkstra 演算法解決單源最短路徑問題：給定起點 $s$，求 $s$ 到所有其他頂點的最小權重總和路徑。它的精神類似 BFS，但用優先佇列（priority queue）取代普通 queue，每次從未處理頂點中挑出當前 distance 最小者。

前提：邊權必須非負 Dijkstra 不適用於有負邊權的圖。負邊會讓「拿出最小者就確定其最終距離」這個貪婪假設失效，詳見練習題 1。對於有負邊但無負環的情況請改用 Bellman-Ford。

起點速度

          Priority Queue：
          empty
        

距離表 LIVE

虛擬碼 CODE

#include "pythonds3/cppds/graph.hpp"
#include <climits>#include <functional>#include <queue>#include <stdexcept>#include <vector>
void dijkstraPanel(Graph& g, const string& startKey) {
    if (!g.vertices.count(startKey)) { throw invalid_argument("missing start"); } priority_queue<pair<int,string>, vector<pair<int,string>>, greater<pair<int,string>>> pq;
    for (auto& [key,v] : g.vertices) { v.distance=INT_MAX; v.previous=""; for (auto& edge : v.neighbors) if (edge.second < 0) throw invalid_argument("negative edge"); }
    g.vertices.at(startKey).distance = 0; pq.push({0, startKey});
    while (!pq.empty()) {
        auto [distance, uKey] = pq.top(); pq.pop();
        if (distance > g.vertices.at(uKey).distance) continue;
        for (auto& [vKey, weight] : g.vertices.at(uKey).neighbors) {
            int newDistance = distance + weight;
            if (newDistance < g.vertices.at(vKey).distance) {
                g.vertices.at(vKey).distance = newDistance;
                g.vertices.at(vKey).previous = uKey;
                pq.push({newDistance, vKey}); } } } }

複雜度

時間（heap）$O((|V|{+}|E|)\log|V|)$

初始化 PQ$O(1)$

最多 entries$O(|E|)$

關鍵概念：邊鬆弛 (relaxation) 第 9–13 行稱為邊鬆弛：對 $u$ 的每個鄰居 $v$，檢查是否可以透過 $u$ 走到 $v$ 比目前已知更近： $$\text{new\_d} = d(u) + w(u,v),\quad \text{若 new\_d} < d(v)\text{，更新 } d(v) \text{ 並把 }u\text{ 設為 previous}.$$ 本課程採 lazy priority queue：改善距離時直接 push 新 pair；舊 pair 出列時若距離較大就略過。最多 $O(|E|)$ 次 push/pop；簡單圖上 $\log|E|=O(\log|V|)$，總時間 $O((|V|+|E|)\log|V|)$。

範例圖這是 PDF 上的標準範例（雙向邊）：頂點 $\{u, v, w, x, y, z\}$，邊權如圖所示。從 $u$ 出發，正確的最短路徑樹如下：
u→v: 2　u→x: 1　u→y: 2 (經 x)　u→w: 3 (經 y)　u→z: 3 (經 y)

講義 08 · dijkstra + findPath 的使用畫面

#include <iostream>
#include "pythonds3/cppds/graph_algos.hpp"   // dijkstra + findPath
using namespace std;
 
int main() {
    Graph g;   // 講義的 6 頂點範例圖（雙向邊）
    g.addEdge("u","v",2); g.addEdge("v","u",2); g.addEdge("v","w",3); g.addEdge("w","v",3);
    g.addEdge("w","z",5); g.addEdge("z","w",5); g.addEdge("u","x",1); g.addEdge("x","u",1);
    g.addEdge("u","w",5); g.addEdge("w","u",5); g.addEdge("x","v",2); g.addEdge("v","x",2);
    g.addEdge("x","w",3); g.addEdge("w","x",3); g.addEdge("x","y",1); g.addEdge("y","x",1);
    g.addEdge("y","w",1); g.addEdge("w","y",1); g.addEdge("y","z",1); g.addEdge("z","y",1);
 
    dijkstra(g, "u");
    for (auto& p : g.vertices)   // 頂點: 距離 (previous)
        cout << p.first << ": " << p.second.distance
             << " (" << p.second.previous << ")" << endl;
    for (string v : findPath(g, "u", "z")) cout << v << " ";
    cout << endl;
    return 0;
}
 

預期輸出

u: 0 ()
v: 2 (u)
w: 3 (y)
x: 1 (u)
y: 2 (x)
z: 3 (y)
u x y z

w 的直達候選是 5，最後下修為 3（u→x→y→w）。lazy PQ 會 push 新的 (3,w)，舊的 (5,w) 出列時因 stale 被略過；不需要在 heap 中搜尋並 decrease-key。u 到 z 的最短路是 u x y z，總長 3。

PART 07 · Prim 最小生成樹

Prim：用最小邊權連通整張圖 cppds §9.22

想像線上遊戲要把同一筆訊息傳給所有玩家。最直覺的做法（Host 對每位玩家各送一份）會讓某些路由器重複收到同一個封包。一個更聰明的做法是：找出一棵最小生成樹（Minimum Spanning Tree, MST）：一個無循環的子圖，連通所有頂點，且總邊權最小。

MST 的定義對無向加權連通圖 $G = (V, E)$，最小生成樹 $T$ 是 $E$ 的一個無循環子集，滿足：
(1) $T$ 連通所有 $V$ 中的頂點；(2) $T$ 中的邊權總和最小。

Prim 是貪婪演算法 Prim 每一步都選「安全邊（safe edge）」：一條跨越「已加入樹的頂點集合」與「尚未加入的頂點」的最小權重邊。每次加入一條，直到所有頂點都進樹為止。
（在實作中我們用 PQ 維護「每個未加入頂點到已加入集合的最小距離」，跟 Dijkstra 結構非常類似！）

連通性前提不連通圖不存在涵蓋所有頂點的 spanning tree。課程的 void prim() 在 PQ 清空後檢查已入樹頂點數；若不足便丟出 invalid_argument，不會靜默回傳 forest。

起點速度

          Priority Queue：
          empty
        

即時統計 LIVE

已加入節點0/0

MST 總權重0

MST 邊清單

—

虛擬碼 CODE

#include "pythonds3/cppds/graph.hpp"#include <climits>#include <functional>#include <queue>#include <set>#include <stdexcept>#include <vector>
void primPanel(Graph& g, const string& startKey) {
    if (!g.vertices.count(startKey)) { throw invalid_argument("missing start"); } priority_queue<pair<int,string>, vector<pair<int,string>>, greater<pair<int,string>>> pq; set<string> inTree;
    for (auto& [key,v] : g.vertices) v.distance = INT_MAX;
    for (auto& [key,v] : g.vertices) v.previous = "";
    g.vertices.at(startKey).distance = 0;
    pq.push({0, startKey});
    while (!pq.empty()) {
        auto [key,uKey]=pq.top(); pq.pop(); if (inTree.count(uKey)) continue; inTree.insert(uKey);
        for (auto& [vKey,weight] : g.vertices.at(uKey).neighbors) {
            int newDistance = weight;
            if (!inTree.count(vKey) && newDistance < g.vertices.at(vKey).distance) {
                g.vertices.at(vKey).previous = uKey;
                g.vertices.at(vKey).distance = newDistance;
                pq.push({newDistance,vKey}); } } } if (inTree.size() != g.vertices.size()) throw invalid_argument("disconnected graph"); }

複雜度

時間（heap）$O((|V|{+}|E|)\log|V|)$

Prim vs Dijkstra：一個關鍵差異結構幾乎一樣，但更新規則不同：
Dijkstra： newD = u->distance + w(u,v)：累加從起點走到 v 的整條路徑權重。
Prim： newD = w(u,v)：只看 u 到 v 的單一邊權。
為什麼？因為 MST 不在乎「離起點多遠」，只在乎「下一個要連入樹的最便宜邊」。

講義 08 · prim 的使用畫面：長出 MST

#include <iostream>
#include "pythonds3/cppds/graph_algos.hpp"   // prim
using namespace std;
 
int main() {
    Graph g;   // 講義的廣播範例圖（雙向邊）
    g.addEdge("A","B",2); g.addEdge("B","A",2); g.addEdge("A","C",3); g.addEdge("C","A",3);
    g.addEdge("B","D",1); g.addEdge("D","B",1); g.addEdge("B","C",1); g.addEdge("C","B",1);
    g.addEdge("B","E",4); g.addEdge("E","B",4); g.addEdge("D","E",1); g.addEdge("E","D",1);
    g.addEdge("C","F",5); g.addEdge("F","C",5); g.addEdge("E","F",1); g.addEdge("F","E",1);
    g.addEdge("F","G",1); g.addEdge("G","F",1);
 
    prim(g, "A");
    cout << "MST edges: ";
    for (auto& p : g.vertices)
        if (p.second.previous != "")
            cout << "(" << p.second.previous << "," << p.first << ") ";
    cout << endl;
    return 0;
}
 

預期輸出

MST edges: (A,B) (B,C) (B,D) (D,E) (E,F) (F,G)

六條邊總權重 7。每次選的是跨越「目前樹／樹外頂點」之 cut 的最小權重 safe edge。

PART 08 · 拓撲排序

拓撲排序：把 DAG 攤平成一條合法的待辦順序 cppds §9.17 · 官方選讀

這是 cppds 正文章節；課程標為 Optional，但保留完整可見摘要供自學。

講義用煎鬆餅開場：食譜很簡單（1 顆蛋、1 杯鬆餅粉、1 匙油、3/4 杯牛奶），難的是先做哪一步。加熱煎鍋和打蛋都可以先做，但「倒麵糊」一定要等鍋熱了、糊攪好了。把每個步驟當頂點、「必須先做」當有向邊，就得到一張 DAG（有向無環圖）。 拓撲排序（topological sort）吃進一張 DAG，吐出一個線性順序，保證圖中每條邊 $(v, w)$ 的 $v$ 都排在 $w$ 前面。凡是「事件有先後依賴」的問題都用得上：軟體專案排程、資料庫查詢最佳化、矩陣連乘的順序安排。

演算法：DFS 的一個小改裝 ① 對圖跑 dfs(g)，目的是替每個頂點算出 closing time（結束時間）。
② 把頂點依 closing time 遞減排成一列。
③ 這一列就是拓撲排序的結果。

速度

節點代號

奶＝3/4 杯牛奶｜蛋＝1 顆蛋｜油＝1 匙油
鍋＝加熱煎鍋｜糊＝攪 1 杯鬆餅糊
漿＝加熱糖漿｜倒＝倒 1/4 杯麵糊
翻＝冒泡就翻面｜吃＝開動

怎麼讀動畫

節點下方的 s/f 是 DFS 的 start／closing time。灰＝已發現、黑＝已完成。第 ② 步只是把黑點照 f 由大到小唸出來，合法的做事順序就出現了。

QUIZ · 為什麼「closing time 遞減」就是答案？

對 DAG 跑完 DFS 後，依 closing time 遞減排序，為什麼保證每條邊 $(v,w)$ 的 $v$ 都排在 $w$ 前面？

(A) 因為 DAG 上有邊 $(v,w)$ 時，$v$ 的 closing time 一定比 $w$ 大

(B) 因為 closing time 大代表這個點的鄰居比較多

PART 09 · 強連通元件

強連通元件（SCC）：找出「彼此都到得了」的頂點群 cppds §9.18 · 官方選讀

這是 cppds 正文章節；課程標為 Optional，但保留完整可見摘要供自學。

把全球資訊網當成一張超大的有向圖：網頁是頂點、超連結是邊。Google 這類搜尋引擎正是在這張圖上做演算法。觀察這種圖會發現：內容相近的網站常常互相連來連去，形成高度互連的群集。抓出這種群集的工具就是強連通元件演算法。正式定義：SCC 是頂點的最大子集 $C \subseteq V$，使得其中任兩點 $v, w$ 都互相可達 （$v$ 到得了 $w$，$w$ 也到得了 $v$）。找到 SCC 之後，把每個 SCC 縮成一顆大點，就得到一張簡化的「元件圖」，原圖的巨觀結構一眼可見。

先備定義：轉置圖 $G^T$ 把 $G$ 的每條邊反向就得到 $G^T$（A→B 變成 B→A）。關鍵觀察：$G$ 和 $G^T$ 的 SCC 一模一樣（「互相可達」反向後仍互相可達），但「跨 SCC」的單向連結會反向。演算法要鑽的正是這個縫。

SCC 演算法四步（Kosaraju） ① 對 $G$ 跑 dfs()，算每個頂點的 closing time。
② 算出轉置圖 $G^T$。
③ 對 $G^T$ 跑 dfs()，但主迴圈依 closing time 遞減的順序挑起點。
④ 步驟 ③ 長出的森林中，每一棵樹就是一個 SCC。

速度

這張例圖

8 個頂點、3 個 SCC：A B E 一圈、C F G 一圈、H I 一圈，圈與圈之間只有單向通道。跑到第 ③ 步會用三種顏色框出三棵樹。

為什麼跑不出去？

第 ③ 步從「closing time 最大」的點出發。在 $G^T$ 裡，通往其他 SCC 的邊全被反向了，DFS 只能在自己的 SCC 裡打轉：一棵樹剛好框住一個元件。

QUIZ · 第二次 DFS 的兩個講究

SCC 演算法的第二次 DFS 為什麼要（i）換到 $G^T$ 上跑、（ii）依 closing time 遞減挑起點？

(A) 兩個條件合起來，讓每棵 DFS 樹恰好「困」在一個 SCC 裡

(B) $G^T$ 的邊比較少，跑起來比較快

EXERCISES · 練習題

動手驗證：兩個經典考點

EXERCISE 1 · Dijkstra 與負邊權

下列圖含負邊權。傳給課程的 dijkstra(g, "A") 時會發生什麼事？

(A) 回傳 A → B → D

(B) 回傳 A → C → D

(D) 在 PQ traversal 前丟出 invalid_argument

EXERCISE 2 · Prim 從 F 出發

下列無向加權圖中，從節點 F 開始執行 Prim 演算法，最後一條被加入 MST 的邊，其權重為何？

(A) 3

(B) 4

(D) 6

REFERENCE · 總覽比較

所有圖演算法一覽

核心演算法比較表

演算法	解決問題	關鍵 DS	時間複雜度	適用條件
BFS	無權最短路徑、連通性	Queue	$O(\|V\|+\|E\|)$	有向／無向皆可
DFS	連通分量、拓撲排序、強連通	Stack（遞迴）	$O(\|V\|+\|E\|)$	有向／無向皆可
Knight's Tour（純 DFS）	Hamiltonian path（特例）	Stack（遞迴）+ backtrack	$O(k^N)$	$N=$ 棋盤格數
+ Warnsdorff 啟發式	同上	同上	啟發式；最壞仍 $O(k^N)$	沒有理論保證
Dijkstra	單源加權最短路徑	Min-heap PQ	$O((\|V\|{+}\|E\|)\log\|V\|)$	邊權必須非負
Prim	最小生成樹	Min-heap PQ	$O((\|V\|{+}\|E\|)\log\|V\|)$	無向連通圖

BFS vs DFS 行為對照

面向	BFS	DFS
探索順序	按距離由近到遠（一層一層）	沿一條分支走到底，再回退
資料結構	FIFO Queue	LIFO Stack（隱式遞迴）
找最短路徑	無權圖直接得到	不保證
記憶體	$O(\|V\|)$（最寬層）	$O(\|V\|)$（最深路徑）
典型應用	最短跳數、層次結構	拓撲排序、SCC、循環偵測、回溯
產生的樹	BFS 樹	DFS forest（多棵樹）

Dijkstra vs Prim：細節差異

面向	Dijkstra	Prim
解決問題	單源最短路徑	最小生成樹
更新規則	`d(u) + w(u,v)` 累加	`w(u,v)` 只看單邊
結果意義	每點到起點的最短距離	連通所有頂點的最小邊集合
邊權限制	不可有負邊	無限制
有向／無向	有向／無向皆可	無向（有向需特殊處理）

學習路線建議 1. 先牢記三色語義（white/gray/black），這是 BFS 與 DFS 共通的骨架。
2. 動手追幾遍 BFS 與 DFS 的虛擬碼：它們程式碼幾乎一樣，差別只在 queue/stack。
3. Dijkstra 與 Prim 同樣是 PQ-based 演算法，只差在更新規則，一起記憶事半功倍。
4. Knight's Tour 是欣賞「啟發式排序」威力的最佳範例：同樣的 DFS 骨架，加上 Warnsdorff 規則就能把 8x8 從「跑不完」變「秒解」。
5. 讀完本頁去 Google Maps Explained 把 BFS、DFS、A* 在真實地圖上各跑一次：觀察加入到終點的估計後，搜尋順序如何改變，再回頭對照本章的距離與優先佇列模型。

QUIZ · 自我檢測

自我檢測：圖演算法課程題庫 ch8 · 6 題

題目取自課程題庫（已譯為繁體中文），每個選項都有解說：選錯也點開看看為什麼錯。全對之後再往下翻詞彙卡。

Q1.為什麼廣度優先搜尋（BFS）在無權重圖上保證找到最短路徑？

Q2.廣度優先搜尋（BFS）與深度優先搜尋（DFS）在「追蹤下一個要探索的頂點」上，主要的結構差異是什麼？

Q3.下列哪一項是 Dijkstra 演算法的已知限制或特性？

Q4.關於圖的實作方式，下列哪個敘述符合教材內容？

Q5.Prim 演算法建最小生成樹（MST）時，什麼是「安全邊」（safe edge）？

Q6.課程的 prim(g, start) 遇到不連通圖時會怎麼做？

CARDS · 關鍵詞彙卡

關鍵詞彙卡：點卡片翻面題庫 ch8.json · 29 張

詞彙卡取自本章課程題庫，已譯為繁體中文，正面附英文原名。先看正面術語，心中默想定義再翻面對答案；洗牌後再過一輪，直到每張都能不假思索說出來。

圖是什麼？先把術語都講清楚 cppds §9.1–9.2

路徑、循環、樹、DAG

頂點的三色狀態（後續演算法都會用到）

怎麼把圖塞進電腦？相鄰矩陣 vs 相鄰串列 cppds §9.3–9.6

相鄰矩陣Adjacency Matrix

相鄰串列Adjacency List

C++ 實作：Vertex 與 Graph 類別 pythonds3/cppds/graph.hpp

講義完整範例：Graph 類別的使用畫面

BFS：一層一層往外擴散 cppds §9.9–9.10

講義完整範例：Word Ladder 的實際執行

Word Ladder：把 BFS 應用到「換字謎題」 cppds §9.7–9.8

建圖技巧：bucket 法（避免 $O(n^2)$ 比對）

DFS：一條路走到黑，碰壁再回頭 cppds §9.15–9.16

Knight's Tour：DFS + Warnsdorff 啟發式 cppds §9.11–9.14

Dijkstra：加權圖上的「貪婪式 BFS」 cppds §9.19–9.21

Prim：用最小邊權連通整張圖 cppds §9.22

拓撲排序：把 DAG 攤平成一條合法的待辦順序 cppds §9.17 · 官方選讀

強連通元件（SCC）：找出「彼此都到得了」的頂點群 cppds §9.18 · 官方選讀

動手驗證：兩個經典考點

所有圖演算法一覽

核心演算法比較表

BFS vs DFS 行為對照

Dijkstra vs Prim：細節差異

自我檢測：圖演算法 課程題庫 ch8 · 6 題

關鍵詞彙卡：點卡片翻面 題庫 ch8.json · 29 張

相鄰矩陣
Adjacency Matrix

相鄰串列
Adjacency List

自我檢測：圖演算法課程題庫 ch8 · 6 題

關鍵詞彙卡：點卡片翻面題庫 ch8.json · 29 張