圖論（Graph Theory）

圖（Graph）

用來表示有限集合中物件之間的關係，物件在圖中以「節點／頂點（node / vertex）」呈現、關係以「邊（edge / arc）」呈現。

一、圖／簡單圖／無向圖（simple graph / undirected graph）

節點之間的邊都沒有方向性，以「直線」呈現。

一張有 3 個節點、3 條邊的無向圖

二、有向圖（directed graph / digraph）

節點之間的邊有方向性，可能為單向或雙向，各自以單箭頭及雙箭頭表示。

一張有 3 個節點、3 條邊的有向圖

三、混合圖（mixed graph）

同時包含有向邊與無向邊的圖。

一張有 3 個節點、2 條有向邊、1 條無向邊的無向圖

四、加權圖／賦權圖／網路（weighted graph / network）

每條邊各自對應一數字，代表其權重（weight），可代表兩相鄰節點關係連結的強弱。

左為「無向加權圖」、右為「有向加權圖」

五、同構（isomorphism）

若兩圖中各自節點形成的集合互為「對射」關係，稱此兩圖為「同構」。

用更簡單的方式理解，「同構」就是「相同構造」，兩張圖的節點個數相同、邊數相同、每個節點各自跟哪個節點連接也相同，唯一不同的是「長的模樣」，但既然是相同構造，兩者會被當成同一種圖研究。

左右兩組圖各自為「同構」關係

特殊的圖

一、正則圖（regular graph）

每個節點的鄰居數量皆相同，即每個節點的「度（degree）」皆相同。若每個節點的度數均為 k，稱為「k-正則圖」。

二、完全圖（complete graph）

每對節點跟節點之間皆僅有一邊連接的無向圖；若為有向圖且每對節點之間皆是雙向關係，稱為「完全有向圖（complete directed graph）」。

三、連通圖（connected graph）

節點與其他節點間至少有一個邊連接的無向圖。

若扣除節點 D，其他 3 個節點與 3 條邊所組成的即為一「連通圖」

對於有限圖來說，若將其所有的邊都改為無向後可形成（簡單）連通圖，稱為「弱連通圖（weakly connected graph）」；若當中任兩節點可透過任一方向連通，稱為「單連通圖（unilaterally connected graph）」；若當中任兩節雙向皆可透過圖中路徑抵達，稱為「強連通圖（strongly connected graph）」。

三者可以各自用更簡單的方式理解：

1. 弱連通圖：把箭頭去掉方向後，沒有節點落單。
2. 單連通圖：每兩個節點間必有至少一個方向可走。
3. 強連通圖：從任一節點出發必能抵達其他所有節點。

四、二分圖／偶圖／雙分圖／二部圖（bipartite graph）

將節點分為兩個互斥的獨立集，每條邊都連接兩個集合內的節點，若其中一集合有 k 個節點、另一個集合有 r 個節點，最多可以形成 k×r 條邊，具有 k×r 條邊的二分圖稱為「完全二分圖（complete bipartite graph）」。

「完全二分圖」示意圖

五、循環圖／環形圖（cycle graph / circular graph）

可形成一單環的簡單圖，邊與節點個數相同，每個節點的度數皆為 2。若要形成循環圖，至少要有三個節點、三條邊。

若一有向圖的邊可形成單環且所有的邊的方向皆相同，稱為「有向循環圖（directed cycle graph）」。

六、樹（tree）

每兩個節點間只有一條邊的無向圖，只要是無單環的連通圖皆可稱之為「樹」。

有根樹（rooted tree）

在「樹」中，可有一節點被指定為「根（root）」，位在整棵樹的頂端。一棵有根樹除了「根」之外，還會有下列構造：

1. 雙親節點／父節點（parent node）：任兩層相連的節點中，較靠近「根」者。
2. 子節點（child node / children）：任兩層相連的節點中，較遠離「根」者，可再依其所在雙親節點的相對位置分為「左子節點（left child）」及「右子節點（right child）」。
3. 手足節點／兄弟節點（sibling node）：所有共享同一雙親節點的同層節點。
4. 堂表手足節點（cousin node）：所有同層但不共享雙親節點的節點。
5. 葉（leaf / leaves）：沒有任何子節點的節點，又稱為「外部節點（external node）」。
6. 內部節點（internal node）：至少有一個子節點的節點。
7. 祖先（ancestor）：指某一節點到根的路徑上所有節點，「根」為所有其他節點的共同祖先。
8. 子嗣／後裔（descendant）：指某一節點往遠離根方向可達的所有節點，至最底層為順著該方向抵達的「葉」。
9. 路徑（path）：連接任兩節點之間所有的邊與節點。
10. 子樹（subtree）：以根以外的節點為新節點形成的小樹，可再依其所在新的根的相對位置分為「左子樹（left subtree）」及「右子樹（right subtree）」。

「樹」構造圖，中&右圖皆以「6號節點」為基準

除上述構造外，「樹」亦包含下列性質：

1. 層（level）：定義根為第 1 層，其餘節點層數為其與根之間連接的邊數 +1。
2. 高度（height）：一節點與最遠的葉間路徑長度，對於「樹」來說，計算基準為其根，故數值與其深度相同。
3. 深度（depth）：一節點與根間路徑長度，對於「樹」來說，計算基準為其距離根最遠的葉，故數值與高度相同。
4. 寬度（width）：指該層節點個數，節點最多那一層的寬度即為「樹」寬度。
5. 寬度（breadth）：葉的個數。
6. 直徑（diameter）：距離最遠的兩葉間路徑長度。

「樹」相關性質示意圖

二元樹（binary tree）

任一雙親節點都只能有不超過 2 個子節點的有根樹。

二元滿樹（full binary tree）

每個節點都有 0 或 2 個節點的二元樹，其葉的數量必為內部節點數量 +1。

完整二元樹（complete binary tree）

最底層節點皆由左而右排列，其他層的節點皆無空缺。

完美二元樹（perfect binary tree）

所有內部節點都有 2 個子節點，且所有葉都在同一層，若高度為 n 層，則所有節點數為 2ⁿ–1。

二元搜尋樹（binary search tree）

對於任一節點而言，其左子節點最小、自己次之、右子節點最大的二元樹。

森林（forest）

指無單環的圖，跟「樹」相比，可能有不連通處，也可理解為多棵互斥的樹形成的集合。

遍歷（traversal）

指在圖中拜訪每個節點。當我們以「圖」的方式儲存資料時，「遍歷」就是在眾多資料內容中找到目標的方法。

一、節點關係呈現方式

在表示圖中節點與節點間的關係時，可以使用「鄰接表」或「鄰接矩陣」方式呈現。

鄰接表（adjacency list）

使用無序列表（unordered list）列出與每個節點相鄰的節點，範例如下：

鄰接矩陣（adjacency matrix）

以矩陣方式呈現兩節點間的關係，若有邊連接記為「1」、無邊連接記為「0」。

在上述範例中，僅為呈現「一步是否可抵達」的狀況，若要檢視「是否可以兩步抵達」，則可將鄰接矩陣乘以鄰接矩陣自己，得走兩步的「可達性矩陣（reachability matrix）」：

等號右方為走兩步的「可達性矩陣」

等號右方矩陣不僅告訴我們走兩步「能不能抵達」，還告訴我們從某節點走兩步可抵達另一對應節點的「總方法數」，舉例如下：

從 A 走兩步到 A，矩陣元素值為 2，代表用兩步從 A 走到 A 的方法共 2 種：

1. A→B→A
2. A→E→A

從 A 走兩步到 B，矩陣元素值為 0，代表用兩步從 A 走到 B 的方法共 0 種：

1. 無法達成

從 B 走兩步到 B，矩陣元素值為 3，代表用兩步從 B 走到 B 的方法共3種：

1. B→A→B
2. B→C→B
3. B→D→B

設「走一步」可到的可達性矩陣為 M，則走兩步的可達性矩陣為 M²、走三步的可達性矩陣為 M³...，依此類推，走 n 步的可達性矩陣為 Mⁿ。

若節點非常多，根據「小世界網路（small-world network）」，任兩節點若要抵達彼此，走的步數大約都只要十步以內就能辦到，遠比想像中來得快。

二、遍歷問題分類

根據邊或節點是否可重複拜訪，以及是否探討最短路徑，主要可分為歐拉路徑問題、哈密頓路徑問題、中國郵遞員問題、旅行推銷員問題四種。

歐拉路徑問題／一筆畫問題（Eulerian graph）

所有的邊都只拜訪過一次，節點可重複拜訪。

現在我們來比較以下三張圖，哪些圖可以透過一筆畫走完所有的邊呢？

依序比較三張圖，可發現：

1. 左圖：C、F、G 三節點都只跟一條邊相連，只能取任兩節點為起、終點，與剩下那一個節點相連的邊必會走過兩次；其他節點皆不能做為起、終點，否則與其相連的邊必無法都只走過一次。
2. 中間圖：可取 A、C 為起、終點，用一筆畫走完所有節點。
3. 右圖：不管取哪兩個節點為起、終點，都可以用一筆畫走完所有節點。

總結來說，若要使用一筆畫走完一圖中所有的邊、每條邊都只經過一次，必須符合下列任一種條件：

1. 起點與終點度數必為奇數、中間節點度數必為偶數：起點僅供離開、終點僅供抵達，中間節點有進必有出。
2. 所有節點度數均為偶數：所有節點都有進必有出。

哈密頓路徑問題（Hamiltonian path problem）

所有的節點都只拜訪一次，邊可重複拜訪。

以下圖而言，左圖可沿箭頭方向完成「哈密頓路徑」，右圖因E節點為「十字路口」，若要抵達 D 節點與 D 節點，E 節點必定要經過兩次，故不可能找到「哈密頓路徑」。

左圖可找到哈密頓路徑，右圖不可

哈密頓路徑問題是一個「NP 完全問題（NP-Complete problem）」，意即該問題的困難度極高，目前僅能以「回溯法（backtracking）」暴力解開，時間複雜度呈指數變化，除此之外，尚無其他更有效率的演算法可解決此問題。

中國郵遞員問題（Chinese postman problem）

所有的邊都至少經過一次且可重複經過。

可以想像有一位郵差要走遍所有的街道送信，每條街道可以重複走過，要如何使送信路徑為最短。

如果是無向圖，這個問題相對容易解決，屬於「P 問題（P problem）」，但若為有向圖，則該問題亦為「NP 完全問題（NP-Complete problem）」，目前僅能以時間複雜度極高的暴力法解開。

旅行推銷員問題（travelling salesman problem, TSP）

已知所有節點與邊的權重，求在每個節點都只經過一次的情況下，可能的最短距離，也就是要找出最短的哈密頓路徑。

可假想有一名推銷員正在多個城市間出差，已經知道所有要拜訪的地點，也知道任兩地點間的距離，要如何在每座城市都只拜訪一次的情況下，使旅行距離為最短。

這個問題同樣是「NP 完全問題（NP-Complete problem）」，目前除了使用「分支定界法（branch and bound）」暴力解開外，尚無其他更有效率的演算法可解決。

三、最短路徑問題（shortest path problem）

探討在加權圖中的任兩節點間移動時，如何能有最小的權重，也就是要如何用最短的距離從某節點移動到某節點。

佛洛依德演算法（Floyd–Warshall algorithm）

從圖中任一節點出發，找出從該節點到其他節點的最短路徑；因使用三層迴圈讓任兩節點配對比較，時間複雜度為 O(n³)。

我們可以透過下列範例，認識「Floyd–Warshall 演算法」的運作方式：

「Floyd–Warshall 演算法」的第一步驟共包含三個部分：

1. 將所有節點自己到自己的路徑長設為 0。
2. 兩節點間路徑存在者，其路徑長設為連結兩節點邊的權重。
3. 其他所有不相連節點間的路徑長設為 ∞。

完成後可得下圖右表，表中數字代表從 i 到 j 的路徑長。

「Floyd–Warshall 演算法」的第二步驟要找出兩節點間距離較短的路徑。

從 i 節點走到 j 節點時，可以直接從 i 走到 j，也可以從 i 經過 k 再到 j，兩者取距離較短者。將所有節點配對、一一比較後可得下圖結果，圖中上半部為第一步驟所得結果，供進行第二步驟時參考；下列三表標黃底處代表路徑較短的走法：

因發現從 A 節點經 B 節點到 C 節點的路徑長，會比 A 節點直接走到 C 節點短，因此將表中 i=A、j=C 中的數字從 4 改為 3，其餘表格內的數字因未找到更短路徑，故維持不變。

經「Floyd–Warshall 演算法」透過上述流程讓任兩節點互相配對進行判斷，最終可得任兩節點間最短路徑如下：

經「Floyd–Warshall 演算法」計算得從 i 到 j 最短路徑表

戴克斯特拉演算法（Dijkstra’s algorithm）

一般用於尋找從某一節點出發，走到其他所有節點的最短路徑，即「單源最短路徑（single source shortest path）」，類似下個段落中「寬度優先搜尋（breadth-first search, BFS）」概念。

可透過「優先隊列（priority queue）」輔助，隊列以路徑長較小者為優先，稱為「最小優先隊列（minimum priority queue）」。

在最糟的情況下，每條邊跟每個節點都要放進並取出「priority queue」中，時間複雜度為 O(|V|+|E|)；而在「priority queue」中，若用「最小堆積（min-heap）」實現「最小優先隊列」，時間複雜度為 O(log|V|)，因此「Dijkstra 演算法」的時間複雜度為 O((|V|+|E|)·log|V|)，其中 |V| 代表圖中節點個數、|E| 代表邊數。

需要特別留意的是，使用本方法求最短路徑時，每條邊的權重不得為負，否則可能會漏找路徑更短的方法，或在帶負邊的環中不斷繞圈，詳細說明可參考 Stack Overflow。

「Dijkstra 演算法」的步驟如下：

1. 挑定一節點為始發節點 A，A 到所有節點的距離皆預設為 ∞。
2. A 到 A 的路徑長為 0，比原本的 ∞ 短，因此將 A 到 A 的距離改為 0，並將 A 節點與 A 到 A 的路徑長資訊放進「priority queue」中。
3. 依路徑長的數值小至大順序依序拜訪「priority queue」中的節點，檢查從 A 到該節點原有的距離，是否比從 A 節點沿本次路徑經過的距離還短。
4. 若原有距離較短，則不變；若沿本次路徑經過的距離較短，則將 A 到該節點的路徑長與前一個節點資訊更新，並將該節點名稱與路徑長資訊放進「priority queue」中，「priority queue」中的節點順序固定依照路徑長由小到大排列。
5. 重複 3.~4.，直到「priority queue」為空、每個節點都被拜訪過為止。

圖解「Dijkstra 演算法」過程範例如下，黃底節點代表目前所在節點、深棕底節點代表已經拜訪過的節點、黃邊為從目前所在節點離開可抵達的鄰居節點：

1. 原圖，挑定始發節點為 A，A 至各節點路徑長皆預設為 ∞，「priority queue」為空。
   

2. A 到 A 節點的路徑長為 0，比原預設的 ∞ 短，因此將 A 到 A 路徑長改為 0，並將 A 節點放進「priority queue」中。
   

3. 拜訪「priority queue」路徑長最短的 A 節點，從 A 出發可抵達 B、C 兩節點。
   

分別判斷 A 到 B、C 兩節點的路徑長：

B 節點：預設從 A 到此的路徑長為 ∞，實際從 A 到此的路徑長為 2，實際路徑較短，故將 B 的前一個節點改為 A，路徑長改為 2，並將 B 節點放進「priority queue」中。

C 節點：預設從 A 到此的路徑長為 ∞，實際從 A 到此的路徑長為 5，實際路徑較短，故將 C 的前一個節點改為 A，路徑長改為 5，並將 C 節點放進「priority queue」中。

目前 A 到 B 的路徑長較 A 到 C 短，故在「priority queue」中，以 B 節點為優先。

1. 拜訪「priority queue」路徑長最短的 B 節點，從 B 出發可抵達 C、D 兩節點。
   

分別判斷 A 到 C、D 兩節點的路徑長：

C 節點：在步驟 3. 得從 A 到此的路徑長為 5，但從 A 經過 B 到此的路徑長為 2+2=4，經過 B 節點路徑較短，故將 C 的前一個節點改為 B，路徑長改為 4，並將「priority queue」中 C 節點的路徑長資訊改為 4。

D 節點：預設從 A 到此的路徑長為 ∞，實際從 A 經 B 到此的路徑長為 2+3=5，實際路徑較短，故將 D 的前一個節點改為 B，路徑長改為 5，並將 D 節點放進「priority queue」中。

目前 A 到 C 的路徑長較 A 到 D 短，故在「priority queue」中，以 C 節點為優先。

1. 拜訪「priority queue」路徑長最短的 C 節點，從 C 出發可抵達 E 節點。
   

判斷 A 到 E 兩節點的路徑長：

原預設 A 到 E 節點路徑長為 ∞，實際從 A 經 B、C 到此的路徑長為 2+2+2=6，實際路徑較短，故將 E 的前一個節點改為 C，路徑長改為 6，並將 E 節點放進「priority queue」中。

目前 A 到 D 的路徑長較 A 到 E 短，故在「priority queue」中，以 D 節點為優先。

1. 拜訪「priority queue」路徑長最短的 D 節點，從 D 出發可抵達 E 節點。
   

判斷 A 到 E 節點的路徑長：

因步驟 5. 所求從 A 到 E 節點路徑長為 6，實際從 A 經 B、D 到此的路徑長為 2+3+4=9，既有路徑較短，故 E 的前一個節點維持為 C、路徑長保持為 6，E 在「priority queue」中的路徑長也維持不變。

1. 拜訪「priority queue」路徑長最短的 E 節點，至此所有節點皆拜訪完畢，不需再判斷 E 到其他節點的路徑長。
   

抵達最後的 E 節點時，我們即可以知道從 A 出發到每個節點的最短路徑，包含「路徑長」與「經過節點」兩項資訊。例如要從 A 節點走到 E 節點，應遵循「A→B→C→E」方式，方能使路徑最短，路徑長為 6，若走「A→B→D→E」或「A→C→B→D→E」都會讓路徑變長。

四、遍歷方式

圖的遍歷方式可分為「寬度優先搜尋（breadth-first search, BFS）」與「深度優先搜尋（depth-first search, DFS）」兩種，前者以「隊列／佇列（queue）這種資料型別輔助、後者以「堆疊（stack）」輔助。

「queue」表示先進到其中的資料將先被處理，即「先進先出（First-In-First-Out, FIFO）」，就如同排隊時，先加入隊伍的人可以比後加入隊伍人的先享受到服務。

「stack」表示後進到其中的資料將先被處理，即「後進先出（Last In First Out, LIFO）」，就如同拿取堆疊的物品時，要先將上層物品取出，才能取得下層物品。

寬度優先搜尋（breadth-first search, BFS）

從某一節點開始，依序找到與各節點連接的所有節點，直到所有節點都被拜訪過為止；在每個節點中確認其相鄰的節點是否被拜訪過時，使用「queue」輔助實現。

在下圖範例中，遍歷從 A 點出發，「visited nodes」代表已經遍歷過的節點、「queue」代表每個與正被拜訪的節點相鄰的節點中，未被拜訪過者。隨著遍歷過程演進，「queue」當中的值會依照「先進先出」規則，依序被放進「visited nodes」。

由 A 節點出發的 BFS 示意圖，已拜訪的節點底色以深棕色表示

直觀上來說，BFS 的遍歷方式有如從某一節點一層一層往外擴。以上圖來說，可把 A 想為第一層，與 A 相連的 B、C 想為第二層，與 B、C 相連的 D、F 想為第三層，與 D 相連的 E 想為第四層；比較到同一層時，該層中任一節點先被放進「queue」中皆可。

深度優先搜尋（depth-first search, DFS）

從某一節點出發，依序拜訪兩相鄰節點，若遇重複拜訪的節點則沿原路返回，直到退回至出發節點為止；在每個節點中確認其相鄰的節點是否被拜訪過時，使用「stack」輔助實現。

在下圖範例中，遍歷從 A 點出發，「visited nodes」代表已經拜訪過的節點、「stack」代表每個與正被拜訪的節點相鄰的節點中，尚未被提出判斷是否放進「visited nodes」者。隨著遍歷過程演進，「stack」當中的值會依照「後進先出」規則，依序被放進「visited nodes」。

由 A 節點出發的 DFS 示意圖，已拜訪的節點底色以深棕色表示

直觀上來說，DFS 的遍歷方式有如從某一節點開始出發開始到處探索，走到死胡同或找不到還沒走過的節點就原路折返，直到退回原出發點為止。

五、樹遍歷（tree traversal）

「樹」是一種常見的資料結構，因此樹的遍歷常被詳加探討。

跟「圖」的遍歷一樣，樹遍歷的方式共可分「寬度優先搜尋（BFS）」與「深度優先搜尋（DFS）」兩大類。

寬度優先搜尋（breadth-first search, BFS）

由根開始，每層皆由最左至右，走到每層最右邊節點後，接下層最左邊節點。跟「圖」相比，樹的 BFS 更有一層一層依序往下的感覺。

節點中的數字代表「寬度優先搜尋（BFS）」遍歷順序

深度優先搜尋－前序遍歷（preorder traversal）

從根出發後一路往左下走，抵達最左下角的節點後，在每一層中都走到最右邊的節點再往上層走。

簡單來說，對於每個子樹而言，遍歷順序為「根、左子節點、右子節點」。

節點中的數字代表「前序（preorder）」遍歷順序

深度優先搜尋－中序遍歷（inorder traversal）

從最左下角的節點出發，先把最靠近左下角的節點都走過再往根走，最後走右邊。

簡單來說，對於每個子樹而言，遍歷順序為「左子節點、根、右子節點」。

節點中的數字代表「中序（inorder）」遍歷順序

深度優先搜尋－後序遍歷（postorder traversal）

從最左下角的節點出發，由左至右把下層節點走完，再往上一層走。

簡單來說，對於每個子樹而言，遍歷順序為「左子節點、右子節點、根」。

節點中的數字代表「後序（postorder）」遍歷順序

樹遍歷「深度優先搜尋（DFS）」小結

1. 左子節點必定先於右子節點。
2. 根在左子節點之前先走過，稱為「preorder」。
3. 根在兩子節點之間走過，稱為「inorder」。
4. 根在走完兩子節點後才走過，稱為「postorder」。

小結

1. 圖：表示物件之間關係，以「節點」表示物件、「邊」表示節點間關係。
2. 簡單圖：邊無方向的圖。
3. 有向圖：邊有方向的圖，可能為單向或雙向。
4. 混合圖：包含有向邊與無向邊的圖。
5. 加權圖：邊有「權重」的圖。
6. 同構：圖的架構相同，僅外觀不同。
7. 正則圖：每個節點同度。
8. 完全圖：任兩節點間皆有一邊連結，若為有向圖，則所有的邊皆為雙向。
9. 連通圖：沒有節點落單，若為有向圖，可再分為「弱連通圖」、「單連通圖」與「強連通圖」。
10. 二分圖：節點可分為兩部分。
11. 循環圖：可形成單環，若為有向圖，則所有邊的方向相同。
12. 樹：無環的連通圖。
13. 有根樹：可有一節點為「根」，除此之外另可有雙親節點、左右子節點、手足節點、堂表手足節點、葉、內部節點、祖先、子嗣、路徑、左右子樹構造，以及層、高度、深度、寬度、直徑等性質。
14. 二元樹：任一雙親節點的子節點數量不超過 2 個。
15. 二元滿樹：任一節點的子節點數量皆為 0 或 2。
16. 完整二元樹：非最底層節點無空缺，最底層節點由左到右排列。
17. 完美二元樹：所有內部節點都有 2 個子節點，且葉都在同層。
18. 二元搜尋樹：任一子樹數值大小順序為「左子節點≥根≥右子節點」。
19. 森林：無環、但可不連通的圖。
20. 遍歷：拜訪圖中節點。
21. 鄰接表：用無序列表表示節點間是否可互達。
22. 鄰接矩陣：用矩陣表示節點間是否可互達，其乘冪代表走幾步可從某節點走到其他節點或回到原節點，稱為「可達性矩陣」。
23. 歐拉路徑問題：節點可重複拜訪，邊都只走過一次，條件為起點跟終點都必接奇數條邊、中間節點都必接偶數條邊，或者全部節點都連接偶數條邊。
24. 哈密頓路徑問題：節點只拜訪一次，邊可重複拜訪，屬於 NP 完全問題，目前只能用回溯法暴力解開。
25. 中國郵遞員問題：所有邊都至少經過一次且可重複經過，無向圖是 P 問題、有向圖是 NP 完全問題。
26. 旅行推銷員問題（TSP）：節點只拜訪一次，邊可重複拜訪，求最短路徑，屬於 NP 完全問題，目前只能用分支定界法暴力解開。
27. 最短路徑問題：在加權圖中用總權重最小的方式從一節點移動到另一節點。
28. Floyd–Warshall 演算法：求任兩節點間最短路徑，時間複雜度為 O(n³)。
29. Dijkstra 演算法：求單緣最短路徑，以優先隊列輔助，不可用於有負邊的圖，時間複雜度為 O((|V|+|E|)·log|V|)。
30. 隊列（queue）：類似排隊，先進先出。
31. 堆疊（stack）：類似堆東西，後進先出。
32. 寬度優先搜尋（BFS）：一層一層往外拜訪所有節點；用「queue」輔助實現。
33. 深度優先搜尋（DFS）：逐一拜訪所有節點，遇到死胡同或拜訪過的節點時折返，最終回到原節點；用「stack」輔助實現。
34. 樹的「寬度優先搜尋（BFS）」：從根開始一層一層往下走，每層內從左往右走。
35. 前序遍歷（preorder）：對於樹中任一節點而言，遍歷順序為「根→左子節點→右子節點」。
36. 中序遍歷（inorder）：對於樹中任一節點而言，遍歷順序為「左子節點→根→右子節點」。
37. 後序遍歷（postorder）：對於樹中任一節點而言，遍歷順序為「左子節點→右子節點→根」。