圖與圖演算法

CONTENTS · 內容目錄

P00引言：圖的術語 P01圖的表示方法 P02廣度優先搜尋 BFS P03Word Ladder P04深度優先搜尋 DFS P05騎士巡邏 Knight's Tour P06Dijkstra 最短路徑 P07Prim 最小生成樹 EX練習題 REF總覽比較表

PROLOGUE · 開場

圖是什麼？先把術語都講清楚

圖（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 相鄰串列

圖的 ADT 主要支援以下操作：set_vertex(v)、add_edge(u, v, w)、get_vertex(key)、get_vertices()、v in g。實作方式有兩種主流選擇——相鄰矩陣（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% 滿）！這就是為什麼實務上幾乎都用相鄰串列。

Python 實作：Vertex 與 Graph 類別

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

class Vertex:
    def __init__(self, key):
        self.key = key
        self.neighbors = {}  # dict: 鄰居 vertex → 權重
    def set_neighbor(self, other, weight=0):
        self.neighbors[other] = weight
    def get_neighbors(self):
        return self.neighbors.keys()

class Graph:
    def __init__(self):
        self.vertices = {}
    def set_vertex(self, key):
        self.vertices[key] = Vertex(key)
    def add_edge(self, from_vert, to_vert, weight=0):
        if from_vert not in self.vertices: self.set_vertex(from_vert)
        if to_vert not in self.vertices: self.set_vertex(to_vert)
        self.vertices[from_vert].set_neighbor(self.vertices[to_vert], weight)
  

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

PART 02 · 廣度優先搜尋

BFS：一層一層往外擴散

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

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

起點速度

          Queue：
          empty
        

即時統計 LIVE

已探索

當前距離

—

頂點狀態表

虛擬碼 CODE

def bfs(start):    start.color = "gray"    start.distance = 0    start.previous = None    queue = Queue()    queue.enqueue(start)    while queue.size() > 0:        current = queue.dequeue()        for nb in current.get_neighbors():            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 應用到「換字謎題」

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：一條路走到黑，碰壁再回頭

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

def dfs(graph):    for v in graph: v.color = "white"    time = 0    for v in graph:        if v.color == "white":            dfs_visit(v)def dfs_visit(u):    u.color = "gray"    time += 1; u.discovery = time    for nb in u.get_neighbors():        if nb.color == "white":            nb.previous = u            dfs_visit(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 in graph 確保每個白色頂點都會啟動一次 dfs_visit，最終得到一片深度優先森林（DF forest）。

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

PART 05 · 騎士巡邏

Knight's Tour：DFS + Warnsdorff 啟發式

騎士巡邏：在 $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

def knight_tour(n, path, u, limit):    u.color = "gray"    path.append(u)    if n < limit:        nbs = order_by_avail(u)  # Warnsdorff!        done = False        for nb in nbs:            if nb.color == "white":                done = knight_tour(n+1, path, nb, limit)                if done: break        if not done:  # backtrack            path.pop()            u.color = "white"        return done    return True

複雜度

純 DFS$O(k^N)$

Warnsdorff幾乎線性

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

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

PART 06 · Dijkstra 最短路徑

Dijkstra：加權圖上的「貪婪式 BFS」

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

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

起點速度

          Priority Queue：
          empty
        

距離表 LIVE

虛擬碼 CODE

def dijkstra(graph, start):    pq = PriorityQueue()    start.distance = 0    pq.insert((0, start))    visited = set()    while not pq.is_empty():        d, u = pq.delete()  # 取最小        visited.add(u)        for v in u.get_neighbors():            if v in visited: continue            new_d = d + u.weight(v)            if new_d < v.distance:                v.distance = new_d                v.previous = u                pq.update(v, new_d)

複雜度

時間（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：用最小邊權連通整張圖

想像線上遊戲要把同一筆訊息傳給所有玩家。最直覺的做法（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

def prim(graph, start):    pq = PriorityQueue()    for vertex in graph:        vertex.distance = sys.maxsize        vertex.previous = None    start.distance = 0    pq.heapify([(v.distance, v) for v in graph])    while not pq.is_empty():        print(pq)        distance, current_v = pq.delete()        for next_v in current_v.get_neighbors():            new_distance = current_v.get_neighbor(next_v)            if next_v in pq and new_distance < next_v.distance:                next_v.previous = current_v                next_v.distance = new_distance                pq.change_priority(next_v, new_distance)

複雜度

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

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

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 從「跑不完」變「秒解」。

圖是什麼？先把術語都講清楚

路徑、循環、樹、DAG

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

怎麼把圖塞進電腦？相鄰矩陣 vs 相鄰串列

相鄰矩陣Adjacency Matrix

相鄰串列Adjacency List

Python 實作：Vertex 與 Graph 類別

BFS：一層一層往外擴散

Word Ladder：把 BFS 應用到「換字謎題」

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

DFS：一條路走到黑，碰壁再回頭

Knight's Tour：DFS + Warnsdorff 啟發式

Dijkstra：加權圖上的「貪婪式 BFS」

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

動手驗證：兩個經典考點

所有圖演算法一覽

核心演算法比較表

BFS vs DFS 行為對照

Dijkstra vs Prim：細節差異

相鄰矩陣
Adjacency Matrix

相鄰串列
Adjacency List