【考試向】資料結構筆記（圖論 Graph Theory）

歡迎你點入本篇文章！我是 LukeTseng，本系列文章主要整理自學資料結構的一些知識，如果你喜歡我的文章，麻煩您不吝嗇的在文章底下按下一顆愛心，或是追蹤我唷～

簡介

1736 年：柯尼斯堡七橋問題（Seven Bridges of Königsberg）

圖學的誕生源於一個經典的數學謎題，在 18 世紀的普魯士城市柯尼斯堡（Königsberg），有一條普列戈利亞河貫穿整座城市，河中有兩個島嶼，並有七座橋將這兩個島嶼與河岸連接起來。

當時的市民在思考一個問題：「有沒有可能從某處出發，走過所有的七座橋，且每座橋只走過一次，最後又回到原點？」

1736 年，瑞士數學家李昂哈德·尤拉（Leonhard Euler）為了解決該問題，發表了圖論史上的第一篇論文，他將這個真實世界的地貌進行了「抽象化」：

• 他把陸地（河岸與島嶼）縮小成「點」。
• 他把連接陸地的橋樑簡化為「線」。

尤拉證明了，要能夠達成上述條件（即著名的尤拉迴圈），所有點所連接的線的數量（分支度）必須都是偶數。而在七橋問題中，所有陸地連接的橋數都是奇數，因此這樣的走法是不存在的。這個將實體問題抽象為點與線的創舉，正式宣告了圖學理論的誕生。

Image Source：https://graphicmaths.com/computer-science/graph-theory/7-bridges/

圖的專有名詞

Image Source：https://www.geeksforgeeks.org/maths/mathematics-graph-theory-basics-set-1/

1. 頂點（Vertex / Node）：圖中的基本單位，代表實體或資料點（例如：城市、人、電腦）。
2. 邊（Edge / Link）：連接兩個頂點的線，代表兩者之間的關係（例如：道路、友誼、網路連線）。
3. 無向圖（Undirected graph）：邊沒有方向性。如果 A 連接到 B，則 B 也連接到 A（例如：雙向道、Facebook 的好友關係），如上圖就是一個無向圖。
4. 有向圖（Directed graph / Digraph）： 邊具有方向性（通常以箭頭表示）。A 指向 B 不代表 B 一定指向 A（例如：單行道、Instagram 的追蹤關係）。
5. 圖（Graph）：由頂點集合（$V$）與邊集合（$E$）所組成的數學結構，記為 $G = (V, E)$。
   • 無向圖中 $(V_1, V_2)$ 和 $(V_2, V_1)$ 代表相同的邊。
   • 有向圖中 $<V_2, V_1>$ 和 $<V_1, V_2>$ 是不同邊。
     • 有向圖中 $<V_1, V_2>$ 的 $V_1$ 代表邊的前端（Head 或稱起點），$V_2$ 代表邊的尾端（Tail 或稱終點）。
   • 有向圖一般寫 digraph；無向圖一般寫 graph。若只寫圖通常都是表示成無向圖。
6. 多重圖（mutigraph）：允許兩個頂點之間有多條邊相連，或是允許邊的起點和終點是同一個頂點（稱為自環 Self-loop）的圖形。
7. 完整圖（complete graph）：在 $n$ 個頂點的無向圖中，假使有 $\frac{n(n - 1)}{2}$ 就稱之。
   • 即圖中任何兩個頂點之間都有一條邊相連就是完整圖。
8. 相鄰（Adjacent）：若兩個頂點之間有一條邊相連，則稱這兩個頂點互為相鄰。
   • 有向圖稱 $<V_1, V_2>$ 為 $V_1$ 是 adjacent to $V_2$，或 $V_2$ 為 adjacent from $V_1$。
9. 附著（Incident）：描述「邊」與「頂點」的關係。若邊 $e$ 連接著頂點 $v$，則稱邊 $e$ 附著於頂點 $v$。
10. 子圖（Subgraph）：從原圖中挑選出部分的頂點與邊所組成的新圖。
    • 假設 $V(G’) \subseteq V(G)$ 及 $E(G’) \subseteq E(G)$ ，稱 $G’$ 是 $G$ 的子圖，如下圖 S 是 G 的部分子圖。
    • 
    • Image Source：http://mathonline.wikidot.com/graphs-and-subgraphs
11. 路徑（Path）：由一連串相鄰頂點所組成的序列，代表從一個起點走到終點的路線。
12. 長度（Length）：一條路徑上的長度是路徑上所有「邊的數量」。
13. 簡單路徑（Simple path）： 在一條路徑中，除了起點和終點可以相同之外，其餘所有的頂點都沒有重複經過。
14. 循環（Cycle）：一條起點與終點相同，且長度至少為 3 的簡單路徑（形成一個封閉的圈）。
15. 連通（Connected）：在「無向圖」中，如果圖內任意兩個頂點之間都存在至少一條路徑，則稱此圖為連通的。
    • 下圖左方紅色處是連通圖，右方是無連通圖，右方因為兩者（一個像三角鐵的跟一個短直線）之間無法連接，所以為無連通圖。
    • 
    • Image Source：https://walkenho.github.io/graph-theory-and-networkX-part2/
16. 連通單元（Connected component）：無向圖中，已經無法再加入其他頂點，且內部所有頂點互相連通的最大連通子圖（maximum connected subgraph），一個不連通的圖會由多個連通單元組成。
    • 如 15. 底下的圖，右邊非連通圖具有兩個連通單元，一個是那個像三角鐵的圖，一個是短直線的圖。
17. 緊密連通（Strongly connected）：針對「有向圖」。若圖中任意兩個頂點 $A$ 和 $B$，都同時存在從 $A$ 到 $B$ 以及從 $B$ 到 $A$ 的路徑。
    • 如下圖，右邊非緊密連通是因為沒有 vertex 2 可到達 vertex 3 的路徑。
    • 
    • Image Source：https://www.cs.emory.edu/~cheung/Courses/253/Syllabus/Graph/strong-conn.html
18. 緊密連通單元（Strongly connected component / SCC）：有向圖中的最大緊密連通子圖。
    • 
    • Image Source：https://www.geeksforgeeks.org/dsa/strongly-connected-components/
    1. 分支度（Degree）：在無向圖中，連接到該頂點的邊的總數量。（附著在頂點的邊數）
       • 若為有向圖，則其分支度為「內分支度 + 外分支度」。
    2. 內分支度（In-degree）：在有向圖中，指向該頂點的邊的數量（有幾條箭頭射入）。
       • 以上圖左邊的 SCC 中的 vertex 1 而言，內分支度是 1，因為射入 1 的線只有 vertex 4 而已。
    3. 外分支度（Out-degree）：在有向圖中，從該頂點指出的邊的數量（有幾條箭頭射出）。
       • 以上圖左邊的 SCC 中的 vertex 1 而言，外分支度是 1，因為 vertex 1 射出的線只有 1 條。

練習題

1. 給定有向圖如下，求其 (1) 子圖、(2) 緊密連通單元（SCC）。

該有向圖可讀成 $V = {1, 2, 3, 4 }$ ，$E = {1 \rightarrow 2, \ 2 \rightarrow 3, \ 3 \rightarrow 2, \ 3 \rightarrow 4 }$

該張有向圖的子圖非常之多，如下：

1. ${1}$
2. ${2}$
3. ${3}$
4. ${4}$
5. ${1, 2}$
6. ${2, 3}$
7. ${3, 2}$ 等等。

其中只有節點 2 和 3 可以互相到達： $2 \rightarrow 3$ 且 $3 \rightarrow 2$ ，所以它們形成同一個緊密連通單元。

SCC	節點	原因
SCC 1	${1}$	節點 1 只能到達 2，但無法從其他節點回到 1
SCC 2	${2,3}$	2 可以到 3，3 也可以回到 2
SCC 3	${4}$	4 沒有邊可以走出去，也無法回到其他節點

因此該張圖的 SCC 為 ${1}, {2,3}, {4}$ 。

---

2. 求以下有向圖每一節點的內分支度以及外分支度：

1. 內：0、外：3
2. 內：1、外：1
3. 內：1、外：1
4. 內：3、外：2
5. 內：1、外：1
6. 內：1、外：1
7. 內：2、外：0

---

3. 求下圖的子圖、連通單元（Connected Component）。

圖中是無向圖，可記成： $V = {1, 2, 3, 4, 5, 6}$ 、 $E = {(1, 2), (1, 3), (2, 5), (3, 5), (4, 6)}$

1. 子圖共有 ${1, 2}$ 、${1, 3}$、${2, 5}$、${3, 5}$、${1, 2, 3}$ 等等更多。
2. 共 2 個連通單元： $C_1 = {1, 2, 3, 5}$ 、 $C_2 = {4, 6}$

圖資料結構表示法

1. 相鄰矩陣（Adjacency Matrix）

假設圖中有 $n$ 個頂點，建立一個 $n \times n$ 的二維矩陣。

矩陣中的每一格代表 $A[i][j]$，即頂點 $i$ 到頂點 $j$ 是否有邊。

通常定義為： $$A[i][j] = \begin{cases} 1, & \text{若 } V_i \text{ 與 } V_j \text{ 有邊} \ 0, & \text{若 } V_i \text{ 與 } V_j \text{ 沒有邊} \end{cases}$$

如何建構一個 Adjacency Matrix？

Image Source：https://www.geeksforgeeks.org/dsa/adjacency-matrix/

圖中節點有 $4$ 個，因此開 $4 \times 4$ 的矩陣。

• 0、1 兩個 vertices 有互相連接的邊，因此看到矩陣的行（左邊直排的那個），將 0 向右對過去找到列（最頂部的）中的 1，填入 1，如圖：
  • 
  • 若寫成數學式則為 $A[0][1] = 1$ 。
• 1 與 0 跟 2 有邊連接，因此也看到矩陣行中的 1，向右對到列中的 0、2 欄位，分別填入 1，接下來以此類推。
  • 若寫成數學式則為 $A[1][0] = 1$ 以及 $A[1][2] = 1$ 。

因為這是無向圖，所以 $A[i][j] = A[j][i]$ ，也就是矩陣會沿著主對角線對稱。

---

再舉一例：

Image Source：https://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/Graphs.html

	1	2	3	4	5	6
1	0	1	0	0	1	0
2	1	0	1	0	1	0
3	0	1	0	1	0	0
4	0	0	1	0	1	1
5	1	1	0	1	0	0
6	0	0	0	1	0	0

---

有向圖的相鄰矩陣

如果是有向圖，則 $A[i][j] = 1$ 表示的是一條有向邊，$i$ 指向 $j$ 節點。

假設 A → B，則代表 $A[A][B] = 1$，但反過來寫 $A[B][A] = 1$ 就錯了，因為是 A 指向 B，而非 B 指向 A。

所以有向圖的相鄰矩陣不一定對稱。

具體實際例子如下圖：

Image Source：https://www.geeksforgeeks.org/dsa/adjacency-matrix/

---

相鄰矩陣的優點

相鄰矩陣最大的優點是查詢兩個點之間有沒有邊非常快。

例如想問 A、D 是否有邊，直接查詢 $matrix[A][D]$ 即可知道。

時間複雜度： $O(1)$

相鄰矩陣的缺點

相鄰矩陣缺點是很佔空間。

只要有 $n$ 個頂點，不管邊多還是少，都一定要開 $n \times n$ 的空間，所以空間複雜度是 $O(n^2)$ 。

假設有 10000 個頂點，則會產生出 1 億個格子，如果實際上只有 20000 條邊，那矩陣裡面大多數都是 0，會非常浪費。

相鄰串列（Adjacency List）

從此開始就不再是建立 $n \times n$ 表格，而只記錄真正存在的邊。

adjacency list 是一個陣列，每個位置對應一個頂點，裡面存放該頂點相鄰的頂點，就是每一個點後方列出所有相鄰的點。

例：

Image Source：https://www.geeksforgeeks.org/dsa/adjacency-list-meaning-definition-in-dsa/

上圖為一張無向圖，共有三個節點 0、1、2，先寫好這三個節點，並為每個節點畫上一個向右的箭頭，接著根據當前節點的邊有連到的節點寫上去。

再舉一例：

則相鄰串列可為：

後面的 0 表示空指標，後方沒有東西可以接了。

相鄰串列的優點

相鄰串列的最大優點是省空間，適合邊很少的圖。

如果圖有 $n = |V|$ 個頂點，$m = |E|$ 條邊，那相鄰串列的空間大約是 $O(m + n)$ 。

相鄰串列的缺點

缺點是查詢某兩點之間是否有邊，通常沒有矩陣快。

例如想問 A 和 D 有沒有邊？若用相鄰串列表示可能就是 A[] -> B[]-> C[0]。

要去 A 的串列裡面找 D，如果 A 連到很多點，就可能要找比較久。

所以查邊的時間通常和該頂點的 degree，也就是相鄰點數量有關。

兩者的比較

比較項目	相鄰矩陣 Adjacency Matrix	相鄰串列 Adjacency List
儲存方式	用 $n \times n$ 二維矩陣	每個頂點存一串相鄰頂點
空間複雜度	$O(n^2)$	$O(n + m)$
查詢兩點是否有邊	很快，$O(1)$	較慢，約 $O(\deg(v))$
列出某點所有鄰居	要掃一整列，$O(n)$	直接看串列，$O(\deg(v))$
適合情況	稠密圖（Dense Graph）	稀疏圖（Sparse Graph）
無向圖特性	矩陣對稱	每條邊通常存兩次
有向圖特性	不一定對稱	只存出邊，除非另外存入邊

圖追蹤（BFS、DFS）

所謂圖追蹤，即有系統地拜訪圖中的每一個頂點，確保不遺漏也不重複。

想像你抵達了一個陌生的城市（圖），城市裡有許多景點（頂點）與道路（邊）。你需要一個策略來逛完所有的景點。

在計算機科學中，有兩種最經典的探索策略：廣度優先搜尋（BFS）與深度優先搜尋（DFS）。

另外圖追蹤的目的有以下三點：

1. 判斷此圖是否連通。
2. 找出此圖的連通單元。
3. 畫出此圖的擴展樹（Spanning Tree）。

廣度優先搜尋（BFS, Breadth-First Search）

BFS 會像是水波一樣擴散、穩扎穩打。

BFS 的探索方式就像是將一顆石頭丟入池塘，漣漪會一圈一圈地向外擴散，會先拜訪距離起點最近的所有頂點，然後再往外推展到下一層。

• 追蹤步驟：
  1. 選擇一個起點。
  2. 拜訪與起點直接相鄰（距離為 1）的所有頂點。
  3. 接著，拜訪距離為 2 的所有頂點（也就是鄰居的鄰居）。
  4. 重複此過程，直到所有頂點都被拜訪過。
  5. 注意：被拜訪過的節點不會被放入佇列。
  • 只要這樣想就好，就是 BFS 會先拜訪完該層所有的相鄰頂點，才去找下一層的其他頂點。
• 背後依賴的資料結構：佇列（Queue）
  • BFS 採用先進先出（FIFO）的排隊機制，先被發現的頂點，就會先被探索它的下一層。
• 常見應用：
  • 尋找最短路徑：在每條路徑距離都相等的無向圖中，BFS 找到的第一個抵達終點的路徑，絕對是最短路徑。（例如：GPS 導航的雛形、社群網路中的共同好友）。
  • 廣播系統：網路封包的傳遞。

例如下圖，從頂點 1 開始走起：

1. 先拜訪頂點 1，再接著將相鄰的頂點 2、3 也加入佇列（該佇列是用於即將被拜訪的頂點）：
2. 接著拜訪 2（pop 出 queue），再把相鄰節點 4 5 放入佇列：
3. 拜訪 3，然後相鄰節點 6 7（six seven）放入佇列：
4. 接著以此類推…

最後就可以得知 BFS 的最終拜訪順序是：1, 2, 3, 4, 5, 6, 7, 8, 9, 10

深度優先搜尋（DFS, Depth-First Search）

DFS 的探索方式就像是在走迷宮，會選擇一條路徑一直往下走，直到撞到死胡同（沒有未拜訪的相鄰頂點）為止，然後再回溯（Backtrack）到上一個有其他岔路的頂點，繼續探索另一條路。

• 追蹤步驟：
  1. 選擇一個起點。
  2. 挑選一個尚未拜訪的相鄰節點，並把它當作新的起點繼續往下拜訪。
  3. 如果當前頂點所有的相鄰頂點都去過了，就回溯（Backtrack）到上一個最近曾被拜訪的頂點。
  4. 重複此過程，直到所有頂點都被拜訪過。
• 背後依賴的資料結構：堆疊（Stack）
  • DFS 採用後進先出（LIFO）的機制，最新發現的岔路會優先走到底。
• 常見應用：
  • 走迷宮遊戲：尋找是否有一條路能到出口。
  • 拓撲排序（Topological Sort）：解決大學排課系統的先修課程問題。
  • 尋找連通單元。

以先前 BFS 的例子為例，以下是 DFS 的例子：

1. 先直接輸出 1（1 為起點）。
2. 將 1 的相鄰節點 2、3 放入堆疊之中（先加入 3 後才能讓 2 優先被拜訪）：
3. 彈出堆疊（節點 2 被彈出），並將 2 的相鄰節點 1、4、5 堆入堆疊當中：
4. 彈出 1 後，因為 1 已經被拜訪過了，因此直接彈出 4，再將其相鄰節點 2、8 堆入堆疊中：
5. 彈出 2，因為 2 被拜訪過，直接彈出 8，再取 8 的相鄰節點 4、5、10 進來：
6. 彈出 4，4 被拜訪過，直接彈出 5，接著再把 5 的相鄰節點 2、8 加進來：
7. 彈出 2、8，因為都被拜訪過了，然後再直接彈出 10，加入其相鄰節點 8、9 進去：
8. 彈出 8，此節點已被拜訪過，因此再彈出 9，並找出它的相鄰節點 6、7、10 加進去：
9. 彈出 6，接著也把相鄰節點 3、9 放進去：
10. 彈出 3，再把相鄰節點 1、6、7 放進去：
11. 彈出 1、6，因為這兩個拜訪過了，所以直接彈出 7，加入其相鄰節點 3、9：
12. 最後沒有任何一個是未被拜訪過的節點了，因此直接彈出所有節點，讓堆疊為空，表示搜尋已結束。

最後拜訪的順序為 1、2、4、8、5、10、9、6、3、7。（需注意該順序並非唯一，而是根據頂點放入堆疊的順序而定）

練習題

求出下圖的 DFS / BFS 追蹤順序：

DFS（堆疊為 [底 -> 頂部]）：

步驟	動作與說明	堆疊狀態 [底 -> 頂]	當前拜訪輸出
0	初始狀態，將起點 1 推入堆疊。	[1]
1	彈出 1。將未拜訪的相鄰點 (8, 6, 3) 依序推入。	[8, 6, 3]	1
2	彈出 3。將未拜訪的相鄰點 (7) 推入。	[8, 6, 7]	1, 3
3	彈出 7。將未拜訪的相鄰點 (5) 推入。	[8, 6, 5]	1, 3, 7
4	彈出 5。將未拜訪的相鄰點 (8, 6, 4) 依序推入。	[8, 6, 8, 6, 4]	1, 3, 7, 5
5	彈出 4。將未拜訪的相鄰點 (6) 推入。	[8, 6, 8, 6, 6]	1, 3, 7, 5, 4
6	彈出 6。所有相鄰點皆已拜訪過。	[8, 6, 8, 6]	1, 3, 7, 5, 4, 6
7	彈出 6。此節點已拜訪過，直接忽略。	[8, 6, 8]	1, 3, 7, 5, 4, 6
8	彈出 8。將未拜訪的相鄰點 (2) 推入。	[8, 6, 2]	1, 3, 7, 5, 4, 6, 8
9	彈出 2。所有相鄰點皆已拜訪過。	[8, 6]	1, 3, 7, 5, 4, 6, 8, 2
10	彈出 6。此節點已拜訪過，直接忽略。	[8]	1, 3, 7, 5, 4, 6, 8, 2
11	彈出 8。此節點已拜訪過，直接忽略。堆疊清空。	[]	1, 3, 7, 5, 4, 6, 8, 2

因此最終 DFS 輸出為 1, 3, 7, 5, 4, 6, 8, 2。

---

BFS（佇列為 [前 -> 後]）：

步驟	動作與說明	佇列狀態 [前 -> 後]	當前拜訪輸出
0	將起點 1 放入佇列。	[1]
1	取出 1。將相鄰且未被發現的點 (3, 6, 8) 放入。	[3, 6, 8]	1
2	取出 3。將相鄰且未被發現的點 (7) 放入。	[6, 8, 7]	1, 3
3	取出 6。將相鄰且未被發現的點 (4, 5) 放入。	[8, 7, 4, 5]	1, 3, 6
4	取出 8。將相鄰且未被發現的點 (2) 放入。	[7, 4, 5, 2]	1, 3, 6, 8
5	取出 7。無未發現的相鄰點（5 已在佇列中）。	[4, 5, 2]	1, 3, 6, 8, 7
6	取出 4。無未發現的相鄰點。	[5, 2]	1, 3, 6, 8, 7, 4
7	取出 5。無未發現的相鄰點。	[2]	1, 3, 6, 8, 7, 4, 5
8	取出 2。無未發現的相鄰點。佇列清空。	[]	1, 3, 6, 8, 7, 4, 5, 2

因此最終 BFS 輸出為 1, 3, 6, 8, 7, 4, 5, 2。

擴展樹（Spanning Tree）

給定一個連通的無向圖 $G = (V, E)$，它的擴展樹是 $G$ 的一個子圖，這個子圖必須滿足兩個條件：

1. 包含圖 $G$ 中所有的頂點 $V$。
2. 是一棵樹（即連通且沒有任何迴圈/循環）。

因為要連接 $n$ 個頂點且不能產生迴圈，一棵擴展樹必定恰好包含 $n - 1$ 條邊。同一個圖通常會有很多種不同的擴展樹。

DFS 與 BFS 生成的擴展樹

可用圖的走訪演算法來輕易建立擴展樹，在走訪過程中，將實際走過的邊保留下來，就會形成擴展樹。

• DFS 擴展樹（深度優先擴展樹）：使用深度優先搜尋（Depth-First Search）走訪圖所產生的樹。
  • DFS 會盡可能往深處探索，因此這棵樹的形狀通常會比較「瘦長」，路徑深度較深。
• BFS 擴展樹（廣度優先擴展樹）：使用廣度優先搜尋（Breadth-First Search）走訪圖所產生的樹。
  • BFS 會由起點向外逐層擴張，因此這棵樹的形狀通常比較「矮胖」。
  • 它的特性是：從起點到樹上任何一個節點的路徑，都是原圖中最少邊數的捷徑。

擴展樹的特性

假設 $G = (V, E)$ 是一張連通圖，而 $S = (V, T)$ 是 $G$ 的擴展樹。其中 $T$ 為生成樹時保留（拜訪過）的邊集合，$K$ 為未被保留（未拜訪）的邊集合。

• 特性 1：$E = T \cup K$ 或是 $E = T + K$
  原圖的邊集合 $E$ 就是擴展樹上的邊 $T$ 與被捨棄的邊 $K$ 的聯集，一個互斥且完備的分割。
• 特性 2：$V$ 的任何兩個頂點 $V_1, V_2$，在 $S$ 中有唯一的「路徑」。
• 特性 3：加入 $K$ 中任何一個邊於 $S$ 中，會造成循環。
  因為 $S$ 已經連通了所有頂點，此時若從 $K$ 中拿任何一條邊加回 $S$ 中，等於在原本已經有路徑的兩點之間又加上了一條捷徑，這必然會形成剛好一個循環。

最小成本擴展樹（Minimum Spanning Tree, MST）

如果圖 $G = (V, E)$ 中的每一條邊都有一個權重（成本），那麼在所有可能的擴展樹中，所有邊的權重總和最小的那棵樹，就稱為最小成本擴展樹。

實作上，這兩種演算法經常會搭配優先佇列（Priority Queue / Min-Heap）或互斥集（Disjoint Set）來達到最佳的時間複雜度。

Prim’s Algorithm（普林演算法）

以「頂點」為中心，從單一節點開始，每次貪婪地尋找能連接到已知集合的最小成本邊，逐步擴張樹的範圍。

演算步驟：

1. 將所有頂點分為兩個集合：已加入樹的 $U$ 以及未加入的 $V - U$，起初 $U$ 只有一個起點（例如 $U = {1}$）。
2. 從 $V - U$ 找出一個頂點，跟 $U$ 頂點能形成最小成本的邊。
3. 將該邊所連接的 $V - U$ 頂點 $x$ 加入 $U$ 集合中。
4. 重複步驟 2 與 3，直到所有頂點都加入 $U$（即 $U = V$）。

範例：

假設有一圖 $V = {1, 2, 3, 4}$，邊與權重如下：(1,2)=1, (1,3)=4, (2,3)=2, (2,4)=5, (3,4)=3 ，選擇頂點 1 作為起點。

$U = {1}$，$V-U = {2, 3, 4}$；成本 $= 0$。

1. 從 $V - U = {2, 3, 4}$ 找一頂點，能與 $U = {1}$ 頂點形成最小成本的邊。
   • 共有 2 個：(1, 2) = 1, (1, 3) = 4。
   • 最小的是 (1,2)，將頂點 2 加入 $U$。
   • $U = {1, 2}$，$V-U = {3, 4}$；成本 $= 1$ （因為 (1, 2) = 1）。
2. 從 $V - U = {3, 4}$ 找一頂點，能與 $U = {1, 2}$ 頂點形成最小成本的邊。
   • 共有 3 個：(1, 3) = 4, (2, 3) = 2, (2, 4) = 5。
   • 最小的是 (2, 3)，將頂點 3 加入 $U$。
   • $U = {1, 2, 3}$，$V - U = {4}$；成本 $= 1 + 2 = 3$ （因為 (1, 2) = 1, (2, 3) = 2, 因此 1 + 2 = 3）。
3. 從 $V - U = {4}$ 找一頂點，能與 $U = {1, 2, 3}$ 頂點形成最小成本的邊。
   • 共有 2 個：(2, 4) = 5, (3, 4) = 3。
   • 最小的是 (3, 4)，將頂點 4 加入 $U$。
   • $U = {1, 2, 3, 4}$，所有頂點皆已加入。
4. 結果：MST 包含邊 (1,2), (2,3), (3,4)，總最小成本為 $6$。

最後結果圖如下（虛線是原本的圖的邊，藍線為最小成本擴展樹）：

Kruskal’s Algorithm（克魯斯克爾演算法）

以「邊」為中心，全局考慮，先將所有邊依權重排序，從最便宜的邊開始挑選，只要不形成迴圈就將其納入樹中。

演算步驟：

1. 準備一個空的邊集合 $T = \emptyset$（即 $T = (V, \phi)$，一開始沒有邊）。
2. 將圖 $G$ 中所有的邊依照成本（權重）由小到大排序。
3. 依序取出成本最小的邊，判斷如果將這條邊加入 $T$ 中是否會形成循環（通常使用 Disjoint Set 來判斷）：
   • 不會形成循環：將這條邊加入 $T$。
   • 會形成循環：捨棄這條邊。
4. 重複步驟 3，直到 $T$ 中收集滿 $n - 1$ 條邊為止。

範例：繼續用上次的圖。

$T = \emptyset$。將所有邊排序：(1,2)=1, (2,3)=2, (3,4)=3, (1,3)=4, (2,4)=5。

1. 取出 (1,2)=1，不會形成迴圈，加入 $T$，$T = {(1,2)}$。
2. 取出 (2,3)=2，不會形成迴圈，加入 $T$，$T = {(1,2), (2,3)}$。
3. 取出 (3,4)=3，不會形成迴圈，加入 $T$，$T = {(1,2), (2,3), (3,4)}$。
4. 結果：此時 $T$ 已有 $4 - 1 = 3$ 條邊，演算法結束，sMST 的總最小成本為 $1 + 2 + 3 = 6$。

最後可以發現其實這兩個演算法生出來的最小擴展樹都長一樣，因為圖相同就不再多放了。

練習題

用 Prim’s 和 Kruskal’s algorithms 求出下圖的最小成本擴展樹：

首先把所有的邊與權重整理出來：

• (4, 6) = 18
• (2, 8) = 21
• (7, 8) = 25
• (1, 3) = 29
• (1, 8) = 31
• (1, 2) = 32
• (4, 5) = 34
• (5, 6) = 40
• (5, 8) = 46
• (1, 7) = 51
• (5, 7) = 51
• (1, 6) = 60

1. Kruskal’s Algorithm：將所有邊依照權重由小到大排序，依序挑選，只要加入該邊不會形成迴圈，就將其納入 MST 中，直到收集到 $8 - 1 = 7$ 條邊為止。
   1. (4, 6) = 18：無迴圈，加入。（目前邊數：1，成本：18）
   2. (2, 8) = 21：無迴圈，加入。（目前邊數：2，成本：39）
   3. (7, 8) = 25：無迴圈，加入。（目前邊數：3，成本：64）
   4. (1, 3) = 29：無迴圈，加入。（目前邊數：4，成本：93）
   5. (1, 8) = 31：無迴圈，加入。（目前邊數：5，成本：124）
   6. (1, 2) = 32：加入會與 (1, 8), (2, 8) 形成迴圈，捨棄。
   7. (4, 5) = 34：無迴圈，加入。（目前邊數：6，成本：158）
   8. (5, 6) = 40：加入會與 (4, 6), (4, 5) 形成迴圈，捨棄。
   9. (5, 8) = 46：無迴圈，加入。（目前邊數：7，成本：204）

最終包含的邊：(4, 6), (2, 8), (7, 8), (1, 3), (1, 8), (4, 5), (5, 8)

最小總成本：204

2. Prim’s Algorithm：從單一節點出發（假設從節點 1 開始），每次從已探索的集合 $U$ 連接到未探索的集合 $V-U$ 的邊中，挑選權重最小的一條，逐步將頂點納入集合，直到所有節點都被探索。

$U = {1}$，$V-U = {2, 3, 4, 5, 6, 7, 8}$；成本 $= 0$。

1. 從 $V - U = {2, 3, 4, 5, 6, 7, 8}$ 找一頂點，能與 $U = {1}$ 頂點形成最小成本的邊。
   • 共有 5 個：(1, 2) = 32, (1, 3) = 29, (1, 6) = 60, (1, 7) = 51, (1, 8) = 31。
   • 最小的是 (1, 3)，將頂點 3 加入 $U$。
   • $U = {1, 3}$，$V-U = {2, 4, 5, 6, 7, 8}$；成本 $= 29$ （因為 (1, 3) = 29）。
2. 從 $V - U = {2, 4, 5, 6, 7, 8}$ 找一頂點，能與 $U = {1, 3}$ 頂點形成最小成本的邊。
   • 共有 4 個：(1, 2) = 32, (1, 6) = 60, (1, 7) = 51, (1, 8) = 31。
   • 最小的是 (1, 8)，將頂點 8 加入 $U$。
   • $U = {1, 3, 8}$，$V - U = {2, 4, 5, 6, 7}$；成本 $= 29 + 31 = 60$ （因為 (1, 3) = 29, (1, 8) = 31, 因此 29 + 31 = 60）。
3. 從 $V - U = {2, 4, 5, 6, 7}$ 找一頂點，能與 $U = {1, 3, 8}$ 頂點形成最小成本的邊。
   • 共有 6 個：(1, 2) = 32, (1, 6) = 60, (1, 7) = 51, (2, 8) = 21, (5, 8) = 46, (7, 8) = 25。
   • 最小的是 (2, 8)，將頂點 2 加入 $U$。
   • $U = {1, 2, 3, 8}$，$V - U = {4, 5, 6, 7}$；成本 $= 60 + 21 = 81$ （因為累積成本 60，加上 (2, 8) = 21，因此 60 + 21 = 81）。
4. 從 $V - U = {4, 5, 6, 7}$ 找一頂點，能與 $U = {1, 2, 3, 8}$ 頂點形成最小成本的邊。
   • 共有 4 個：(1, 6) = 60, (1, 7) = 51, (5, 8) = 46, (7, 8) = 25。
   • 最小的是 (7, 8)，將頂點 7 加入 $U$。
   • $U = {1, 2, 3, 7, 8}$，$V - U = {4, 5, 6}$；成本 $= 81 + 25 = 106$ （因為累積成本 81，加上 (7, 8) = 25，因此 81 + 25 = 106）。
5. 從 $V - U = {4, 5, 6}$ 找一頂點，能與 $U = {1, 2, 3, 7, 8}$ 頂點形成最小成本的邊。
   • 共有 3 個：(1, 6) = 60, (5, 7) = 51, (5, 8) = 46。
   • 最小的是 (5, 8)，將頂點 5 加入 $U$。
   • $U = {1, 2, 3, 5, 7, 8}$，$V - U = {4, 6}$；成本 $= 106 + 46 = 152$ （因為累積成本 106，加上 (5, 8) = 46，因此 106 + 46 = 152）。
6. 從 $V - U = {4, 6}$ 找一頂點，能與 $U = {1, 2, 3, 5, 7, 8}$ 頂點形成最小成本的邊。
   • 共有 3 個：(1, 6) = 60, (4, 5) = 34, (5, 6) = 40。
   • 最小的是 (4, 5)，將頂點 4 加入 $U$。
   • $U = {1, 2, 3, 4, 5, 7, 8}$，$V - U = {6}$；成本 $= 152 + 34 = 186$ （因為累積成本 152，加上 (4, 5) = 34，因此 152 + 34 = 186）。
7. 從 $V - U = {6}$ 找一頂點，能與 $U = {1, 2, 3, 4, 5, 7, 8}$ 頂點形成最小成本的邊。
   • 共有 3 個：(1, 6) = 60, (4, 6) = 18, (5, 6) = 40。
   • 最小的是 (4, 6)，將頂點 6 加入 $U$。
   • $U = {1, 2, 3, 4, 5, 6, 7, 8}$，所有頂點皆已加入。
8. 結果：MST 包含邊 (1, 3), (1, 8), (2, 8), (7, 8), (5, 8), (4, 5), (4, 6)，總最小成本為 $204$。

最終生出來的最小成本擴展樹長這樣（兩個演算法最後生出來的都長一樣）：

最短路徑演算法：Dijkstra’s algorithm

在網路與圖論中最基本的應用問題之一就是：「如何求出某一起點 $V_s$ 到某一終點 $V_t$ 的最短距離或最短路徑？」

想像一張城市地圖，每個路口是一個節點（Node），連接路口的街道是邊（Edge），而街道的長度或塞車時間就是權重（Weight）。

當你打開 Google Maps 規劃從家裡（起點 $V_s$）到公司（終點 $V_t$）的路線時，系統要在無數條可能的路徑中，找出一條總權重（時間或距離）最小的路徑。

為了解決這個問題，荷蘭計算機科學家 Edsger W. Dijkstra 在 1956 年構思出了著名的 Dijkstra’s Algorithm（戴克斯特拉演算法）。

Dijkstra’s Algorithm 的特點：

1. 用途：解決單一源點（Single-source）到其他所有節點的最短路徑問題。
2. 貪婪法：逐步向外擴展，每次都選擇目前已知距離最短的節點作為下一個探索點。
3. 限制： 圖中不可以有負權重的邊（Negative weight edges）。如果路徑上有負數權重，Dijkstra 會因為提早把節點標記為「已確定最短距離」而導致計算錯誤（若有負權重，通常會改用 Bellman-Ford 演算法）。

Dijkstra’s Algorithm 演算步驟

演算法在執行時，會為每個節點維護兩個狀態：

1. 目前已知最短距離（Distance）：從起點到該節點的暫時最短距離。
2. 拜訪狀態（Visited）：記錄該節點是否已經找到真正的最短路徑。

具體步驟如下：

1. $D[I] = A[F, I] \quad (I = 1, N)$
   $S = {F}$
   $V = {1, 2, \dots, N}$
   $D$ 為 $N$ 個位置的陣列，用來儲存某一頂點到其他頂點的最短距離，$F$ 表示由某一起始點開始，$A[F, I]$ 是表示 $F$ 點到 $I$ 點的距離，$V$ 是網路中所有頂點的集合，$S$ 也是頂點的集合。
2. 從 $V-S$ 集合中找一頂點 $t$，使得 $D[t]$ 是最小值，並將 $t$ 放入 $S$ 集合，一直到 $V-S$ 是空集合為止。
3. 根據下面的公式調整 $D$ 陣列中的值。$$D[I] = \min(D[I], D[t] + A[t, I]) \quad ((I, t) \in E)$$
   • 此處 $I$ 是指 $t$ 的相鄰各頂點，做完後接著繼續回到步驟 2 執行。

範例

下圖是一個有向圖，設定起始點 $F = 1$。

初始狀態如下：

• $F = 1$
• $S = {1}$
• $V = {1, 2, 3, 4, 5, 6, 7}$
• 未加入的最短路徑集合 $V-S = {2, 3, 4, 5, 6, 7}$
• $D = {0, 4, 6, 6, ∞, ∞, ∞}$ （對應頂點 1 到 7）

1. 第 1 次執行：
   • 從 $V-S$ 找出 $D$ 值最小的頂點，得到 $t = 2$。
   • 加入 $S$ 集合：$S = {1, 2}$
   • 步驟 3 調整 $D$ 陣列：
     • 更新 $I = 3$：$\min(6, 4 + 1) = 5$
     • 更新 $I = 5$：$\min(∞, 4 + 7) = 11$
   • 當前 $D$ 陣列：[0, 4, 5, 6, 11, ∞, ∞]
2. 第 2 次執行：
   • 從 $V-S$ 找出 $D$ 值最小的頂點，得到 $t = 3$。
   • 加入 $S$ 集合：$S = {1, 2, 3}$
   • 步驟 3 調整 $D$ 陣列：
     • 更新 $I = 5$：$\min(11, 5 + 6) = 11$
     • 更新 $I = 6$：$\min(∞, 5 + 4) = 9$
   • 當前 $D$ 陣列：[0, 4, 5, 6, 11, 9, ∞]
3. 第 3 次執行：
   • 從 $V-S$ 找出 $D$ 值最小的頂點，得到 $t = 4$。
   • 加入 $S$ 集合：$S = {1, 2, 3, 4}$
   • 步驟 3 調整 $D$ 陣列：
     • 更新 $I = 3$：$\min(5, 6 + 2) = 5$（無變動）
     • 更新 $I = 6$：$\min(9, 6 + 5) = 9$（無變動）
   • 當前 $D$ 陣列：[0, 4, 5, 6, 11, 9, ∞]
4. 第 4 次執行：
   • 從 $V-S$ 找出 $D$ 值最小的頂點，得到 $t = 6$。
   • 加入 $S$ 集合：$S = {1, 2, 3, 4, 6}$
   • 步驟 3 調整 $D$ 陣列：
     • 更新 $I = 5$：$\min(11, 9 + 1) = 10$
     • 更新 $I = 7$：$\min(∞, 9 + 8) = 17$
   • 當前 $D$ 陣列：[0, 4, 5, 6, 10, 9, 17]
5. 第 5 次執行：
   • 從 $V-S$ 找出 $D$ 值最小的頂點，得到 $t = 5$。
   • 加入 $S$ 集合：$S = {1, 2, 3, 4, 6, 5}$
   • 步驟 3 調整 $D$ 陣列：
     • 更新 $I = 7$：$\min(17, 10 + 6) = 16$
   • 當前 $D$ 陣列：[0, 4, 5, 6, 10, 9, 16]
6. 此時 $V-S={7}$，加入 $S$ 集合後結束演算法，另外頂點 7 無向外相鄰頂點，陣列無變動。

因此最終 $D$ 陣列為：[0, 4, 5, 6, 10, 9, 16]

每一個都是從 1 頂點開始，前往第 $n$ 個節點的最短距離，如第 7 個頂點跟頂點 1 的最短距離是 16。

---

如何得知頂點 1 到頂點 7 經過哪些節點？假設有一個陣列 $Y$ 如下：[1, 1, 1, 1, 1, 1, 1]。

該 $Y$ 陣列的功能是記錄每一個節點在最短路徑上的上一個節點（也就是從哪裡走過來的）。

$Y$ 更新規則：Relaxation（鬆弛操作），$D[I] > D[t] + A[t, I]$。

• $D[I]$：目前記錄從起點到頂點 $I$ 的最短距離。
• $D[t]$：從起點到頂點 $t$ 的最短距離。
• $A[t, I]$：頂點 $t$ 到頂點 $I$ 的邊長（權重）。

一旦發現了更短的路徑，就必須同時更新 $Y$ 陣列，將 $t$ 放入 $Y[I]$ 中。

表示要想到達節點 $I$ 並且路徑最短，必須先經過節點 $t$。

由上例而言，如何對 $Y$ 陣列做更新：

1. $D[3] > D[2] + A[2, 3]$ ，且 $D[5] > D[2] + A[2, 5]$。
   • 將 2 放在 $Y[3], Y[5]$ -> [1, 1, 2, 1, 2, 1, 1]
2. $D[6] > D[3] + A[3, 6]$。
   • 將 3 放在 $Y[6]$ -> [1, 1, 2, 1, 2, 3, 1]
3. $D[5] > D[6] + A[6, 5]$，且 $D[7] > D[6] + A[6, 7]$。
   • 將 6 放在 $Y[5], Y[7]$ -> [1, 1, 2, 1, 6, 3, 6]。
4. $D[7] > D[5] + A[5, 7]$。
   • 將 5 放入 $Y[7]$ -> [1, 1, 2, 1, 6, 3, 5]。

這樣就做完了，第四步更新的 $Y$ 即為最終的陣列，表示如果要到頂點 7，則必須先經過頂點 5，要經過頂點 5 又要經過頂點 6，等等。

總整理

一、 簡介與核心名詞

圖學源於 1736 年「柯尼斯堡七橋問題」（尤拉證明：要達成尤拉迴圈，所有節點的分支度必須為偶數）。實體問題被抽象化為頂點（Vertex / Node）與邊（Edge / Link），圖記為 $G = (V, E)$。

重要專有名詞

• 圖的種類：
  • 無向圖（Undirected graph）：邊無方向性。$(V_1, V_2)$ 等同 $(V_2, V_1)$。
  • 有向圖（Directed graph / Digraph）：邊有方向性。$<V_1, V_2>$ 代表 $V_1$ 指向 $V_2$。
  • 多重圖（Multigraph）：允許自環（Self-loop）或任兩點間有多條邊。
  • 完整圖（Complete graph）：任兩點間皆有邊相連，無向圖邊數為 $\frac{n(n - 1)}{2}$。
• 頂點關係：
  • 相鄰（Adjacent）：兩頂點間有邊相連。
  • 附著（Incident）：邊連接著某頂點。
• 路徑與循環：
  • 長度（Length）：路徑上「邊的數量」。
  • 簡單路徑（Simple path）：路徑中除起終點外，頂點不重複。
  • 循環（Cycle）：起終點相同的簡單路徑（長度 $\ge 3$）。
• 連通性：
  • 無向圖：
  • 連通（Connected）：圖內任兩點都有路徑。
  • 連通單元（Connected component）：無法再加入點的最大連通子圖。
• 有向圖：
  • 緊密連通（Strongly connected）：任兩點 $A, B$ 皆有 $A \to B$ 及 $B \to A$ 的路徑。
  • 緊密連通單元（SCC）：最大緊密連通子圖。
• 分支度 (Degree)：
  • 無向圖：連接該頂點的邊數。
  • 有向圖：分內分支度（In-degree, 箭頭射入）與外分支度（Out-degree, 箭頭射出）。

---

二、 圖資料結構表示法

比較項目	相鄰矩陣（Adjacency Matrix）	相鄰串列（Adjacency List）
儲存方式	$n \times n$ 二維矩陣	陣列搭配鏈結串列
空間複雜度	$O(n^2)$	$O(n + m)$ ($m$為邊數)
查詢兩點是否有邊	快，$O(1)$	慢，約 $O(\deg(v))$
列出某點所有鄰居	需掃描一整列，$O(n)$	直接掃描該點串列，$O(\deg(v))$
適用圖種	稠密圖（Dense Graph）	稀疏圖（Sparse Graph）
特徵	無向圖矩陣沿主對角線對稱	無向圖每條邊存兩次

---

三、 圖追蹤 (Graph Traversal)

目的：判斷連通性、找連通單元、建立擴展樹。

搜尋法	廣度優先搜尋（BFS）	深度優先搜尋（DFS）
核心概念	像水波般逐層擴散。先拜訪鄰居，再拜訪鄰居的鄰居。	像走迷宮。一條路走到底，遇死胡同才回溯（Backtrack）。
資料結構	佇列（Queue） - FIFO	堆疊（Stack） - LIFO
常見應用	無權重圖的最短路徑、網路廣播	迷宮求解、拓撲排序、找連通單元
擴展樹形狀	矮胖型（路徑為最短捷徑）	瘦長型（深度較深）

---

四、 擴展樹 (Spanning Tree)

子圖若包含原圖所有頂點（$n$） 且為樹（連通且無循環），即為擴展樹，必定恰好有 $n - 1$ 條邊。
加入任何一條不在擴展樹上的原圖邊，必定會產生一個循環。

最小成本擴展樹 (MST, Minimum Spanning Tree)

有權重圖中，所有擴展樹裡「邊的權重總和最小」者。

1. Prim’s Algorithm (普林演算法)

• 策略：以「頂點」為中心，貪婪法。
• 步驟：
  1. 將頂點分兩群：已選 $U$、未選 $V-U$ (起初 $U$ 只有一起點)。
  2. 找一條連接 $U$ 與 $V-U$ 且權重最小的邊，將對應的頂點加入 $U$。
  3. 重複直到所有頂點皆加入 $U$。

2. Kruskal’s Algorithm (克魯斯克爾演算法)

• 策略：以「邊」為中心，全局貪婪法（常配互斥集 Disjoint Set）。
• 步驟：
  1. 將所有邊依權重由小到大排序。
  2. 從最小的邊開始挑，若加入該邊不形成循環則選用。
  3. 挑滿 $n - 1$ 條邊即完成。

---

五、 最短路徑演算法：Dijkstra’s Algorithm

求單一源點到其他所有節點的最短路徑。

• 限制：圖中不可有負權重的邊 (若有須改用 Bellman-Ford)。

• 資料維護：

  • $D$ 陣列：記錄起點到各點的「目前最短距離」。
  • $S$ 集合：記錄「已確定最短路徑的頂點」。
  • $Y$ 陣列（選擇性）：記錄路徑的上一個節點 (前驅)，用於追蹤完整路線。

• 演算步驟：

  1. 初始化起點的 $D$ 為 0，其餘為 $\infty$。
  2. 從未加入的頂點 ($V-S$) 中找 $D$ 值最小的點 $t$，加入 $S$。
  3. 鬆弛操作 (Relaxation)：藉由剛加入的 $t$，檢查其相鄰節點 $I$ 是否有更短的路徑：$$D[I] = \min(D[I], D[t] + A[t, I])$$
     (若有更新 $D[I]$，則同步更新 $Y[I] = t$)
  4. 重複步驟 2 與 3，直到所有點皆加入 $S$。