圖與圖演算法

CONTENTS · 內容目錄

P00引言：圖的術語 P01圖的表示方法 P02廣度優先搜尋 BFS P03Word Ladder P04深度優先搜尋 DFS P05騎士巡邏 Knight's Tour P06Dijkstra 最短路徑 P07Prim 最小生成樹 P08拓撲排序（補充） P09強連通元件（補充） EX練習題 REF總覽比較表

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

圖的 ADT 主要支援以下操作：setVertex(v)、addEdge(u, v, w)、getVertex(key)、getVertices()、g.count(v)。實作方式有兩種主流選擇：相鄰矩陣（adjacency matrix）和相鄰串列（adjacency list），兩者各有適用情境。

相鄰矩陣
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|)$

查邊$O(\deg(v))$

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

真實世界：稀疏為主

以後面 Word Ladder 為例：5,110 個字 ⇒ 矩陣 $5{,}110^2 = 26{,}112{,}100$ 格，但實際只有 53,286 條邊（0.20% 滿）！這就是為什麼實務上幾乎都用相鄰串列。

C++ 實作：Vertex 與 Graph 類別 dscpp/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) { vertices[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），但底層結構不變。

PART 02 · 廣度優先搜尋

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

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

核心資料結構 BFS 用一個 Queue（先進先出）決定下一個要造訪的頂點。每個頂點維護三個欄位：color（white/gray/black）、distance（到起點的最短距離）、previous（前驅，用來重建路徑）。

起點速度

          Queue：
          empty
        

即時統計 LIVE

已探索

當前距離

—

頂點狀態表

虛擬碼 CODE

bfs(start):
    start->color = "gray"
    start->distance = 0
    start->previous = NULL
    Queue queue
    queue.enqueue(start)
    while queue.size() > 0:
        current = queue.dequeue()
        for nb : current->getNeighbors():
            if nb->color == "white":
                nb->color = "gray"
                nb->distance = current->distance + 1
                nb->previous = current
                queue.enqueue(nb)
        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|$ 次！

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

dfs(graph):
    for v : graph: v->color = "white"
    time = 0
    for v : graph:
        if v->color == "white":
            dfsVisit(v)
 
dfsVisit(u):
    u->color = "gray"
    time += 1; u->discovery = time
    for nb : u->getNeighbors():
        if nb->color == "white":
            nb->previous = u
            dfsVisit(nb)  // 遞迴
    u->color = "black"
    time += 1; u->closing = 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 深度優先」的搜尋順序！

PART 05 · 騎士巡邏

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

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

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

Warnsdorff 啟發式 下一步永遠選「可走鄰居最少」的格子。直覺：先去角落、邊緣那些「難救援」的格子，避免它們被孤立；中間格子鄰居多，留到最後當跳板。
這個簡單規則讓 8x8 從「跑不完」變成不到一秒就完成：經典的 heuristic 範例。

大小起點速度

即時統計 LIVE

已走步數

回退次數

總探索節點0

結果—

虛擬碼 CODE

knightTour(n, path, u, limit):
    u->color = "gray"
    path.push_back(u)
    if n < limit:
        nbs = orderByAvail(u)  // Warnsdorff!
        done = false
        for nb : nbs:
            if nb->color == "white":
                done = knightTour(n+1, path, nb, limit)
                if done: break
        if !done:  // backtrack
            path.pop_back()
            u->color = "white"
        return done
    return true

複雜度

純 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

dijkstra(graph, start):
    PriorityQueue pq
    start->distance = 0
    pq.insert({0, start})
    set<Vertex*> visited
    while !pq.isEmpty():
        [d, u] = pq.delete()  // 取最小
        visited.insert(u)
        for v : u->getNeighbors():
            if visited.count(v): continue
            newD = d + u->weight(v)
            if newD < v->distance:
                v->distance = newD
                v->previous = u
                pq.update(v, newD)

複雜度

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

建 PQ$O(|V|)$

邊鬆弛$O(|E|\log|V|)$

關鍵概念：邊鬆弛 (relaxation) 第 11–14 行稱為邊鬆弛：對 $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}.$$ 每條邊最多鬆弛一次（因為頂點只會從 PQ 取出一次），所以總共 $O(|E|)$ 次鬆弛，配合 PQ 的 $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)

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 結構非常類似！）

起點速度

          Priority Queue：
          empty
        

即時統計 LIVE

已加入節點0/0

MST 總權重0

MST 邊清單

—

虛擬碼 CODE

prim(graph, start):
    for v : graph:
        v->distance = ∞
        v->previous = NULL
    start->distance = 0
    PriorityQueue pq(graph)
    while !pq.isEmpty():
        [d, u] = pq.delete()
        for v : u->getNeighbors():
            newD = u->weight(v)  // 注意：只看單邊權！
            if pq.contains(v) && newD < v->distance:
                v->previous = u
                v->distance = newD
                pq.update(v, newD)

複雜度

時間（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 不在乎「離起點多遠」，只在乎「下一個要連入樹的最便宜邊」。

PART 08 · 拓撲排序

拓撲排序：把 DAG 攤平成一條合法的待辦順序 cppds §9.17 · 講義補充

課堂投影片跳過本節（RISE skip，講義標 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 · 講義補充

課堂投影片跳過本節（RISE skip，講義標 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 演算法（且會檢查 visited 節點，已造訪不再更新），從 A 出發走到 D，最後得到的路徑會是？

(A) A → B → D

(B) A → C → D

(D) A → C → E → G → D

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 啟發式	同上	同上	幾乎線性（實務）	沒有理論保證
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 從「跑不完」變「秒解」。

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

路徑、循環、樹、DAG

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

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

相鄰矩陣Adjacency Matrix

相鄰串列Adjacency List

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

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

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：細節差異

相鄰矩陣
Adjacency Matrix

相鄰串列
Adjacency List