圖（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）」。
三者可以各自用更簡單的方式理解：
- 弱連通圖：把箭頭去掉方向後，沒有節點落單。
- 單連通圖：每兩個節點間必有至少一個方向可走。
- 強連通圖：從任一節點出發必能抵達其他所有節點。
四、二分圖／偶圖／雙分圖／二部圖（bipartite graph）
將節點分為兩個互斥的獨立集，每條邊都連接兩個集合內的節點，若其中一集合有 k 個節點、另一個集合有 r 個節點，最多可以形成 k×r 條邊，具有 k×r 條邊的二分圖稱為「完全二分圖（complete bipartite graph）」。
「完全二分圖」示意圖
五、循環圖／環形圖（cycle graph / circular graph）
可形成一單環的簡單圖，邊與節點個數相同，每個節點的度數皆為 2。若要形成循環圖，至少要有三個節點、三條邊。
若一有向圖的邊可形成單環且所有的邊的方向皆相同，稱為「有向循環圖（directed cycle graph）」。
六、樹（tree）
每兩個節點間只有一條邊的無向圖，只要是無單環的連通圖皆可稱之為「樹」。
有根樹（rooted tree）
在「樹」中，可有一節點被指定為「根（root）」，位在整棵樹的頂端。一棵有根樹除了「根」之外，還會有下列構造：
- 雙親節點／父節點（parent node）：任兩層相連的節點中，較靠近「根」者。
- 子節點（child node / children）：任兩層相連的節點中，較遠離「根」者，可再依其所在雙親節點的相對位置分為「左子節點（left child）」及「右子節點（right child）」。
- 手足節點／兄弟節點（sibling node）：所有共享同一雙親節點的同層節點。
- 堂表手足節點（cousin node）：所有同層但不共享雙親節點的節點。
- 葉（leaf / leaves）：沒有任何子節點的節點，又稱為「外部節點（external node）」。
- 內部節點（internal node）：至少有一個子節點的節點。
- 祖先（ancestor）：指某一節點到根的路徑上所有節點，「根」為所有其他節點的共同祖先。
- 子嗣／後裔（descendant）：指某一節點往遠離根方向可達的所有節點，至最底層為順著該方向抵達的「葉」。
- 路徑（path）：連接任兩節點之間所有的邊與節點。
- 子樹（subtree）：以根以外的節點為新節點形成的小樹，可再依其所在新的根的相對位置分為「左子樹（left subtree）」及「右子樹（right subtree）」。
「樹」構造圖，中&右圖皆以「6號節點」為基準
除上述構造外，「樹」亦包含下列性質：
- 層（level）：定義根為第 1 層，其餘節點層數為其與根之間連接的邊數 +1。
- 高度（height）：一節點與最遠的葉間路徑長度，對於「樹」來說，計算基準為其根，故數值與其深度相同。
- 深度（depth）：一節點與根間路徑長度，對於「樹」來說，計算基準為其距離根最遠的葉，故數值與高度相同。
- 寬度（width）：指該層節點個數，節點最多那一層的寬度即為「樹」寬度。
- 寬度（breadth）：葉的個數。
- 直徑（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 種：
- A→B→A
- A→E→A
從 A 走兩步到 B，矩陣元素值為 0，代表用兩步從 A 走到 B 的方法共 0 種：
- 無法達成
從 B 走兩步到 B，矩陣元素值為 3，代表用兩步從 B 走到 B 的方法共3種：
- B→A→B
- B→C→B
- B→D→B
設「走一步」可到的可達性矩陣為 M，則走兩步的可達性矩陣為 M²、走三步的可達性矩陣為 M³...，依此類推，走 n 步的可達性矩陣為 Mⁿ。
若節點非常多，根據「小世界網路（small-world network）」，任兩節點若要抵達彼此，走的步數大約都只要十步以內就能辦到，遠比想像中來得快。
二、遍歷問題分類
根據邊或節點是否可重複拜訪，以及是否探討最短路徑，主要可分為歐拉路徑問題、哈密頓路徑問題、中國郵遞員問題、旅行推銷員問題四種。
歐拉路徑問題／一筆畫問題（Eulerian graph）
所有的邊都只拜訪過一次，節點可重複拜訪。
現在我們來比較以下三張圖，哪些圖可以透過一筆畫走完所有的邊呢？
依序比較三張圖，可發現：
- 左圖：C、F、G 三節點都只跟一條邊相連，只能取任兩節點為起、終點，與剩下那一個節點相連的邊必會走過兩次；其他節點皆不能做為起、終點，否則與其相連的邊必無法都只走過一次。
- 中間圖：可取 A、C 為起、終點，用一筆畫走完所有節點。
- 右圖：不管取哪兩個節點為起、終點，都可以用一筆畫走完所有節點。
總結來說，若要使用一筆畫走完一圖中所有的邊、每條邊都只經過一次，必須符合下列任一種條件：
- 起點與終點度數必為奇數、中間節點度數必為偶數：起點僅供離開、終點僅供抵達，中間節點有進必有出。
- 所有節點度數均為偶數：所有節點都有進必有出。
哈密頓路徑問題（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 演算法」的第一步驟共包含三個部分：
- 將所有節點自己到自己的路徑長設為 0。
- 兩節點間路徑存在者，其路徑長設為連結兩節點邊的權重。
- 其他所有不相連節點間的路徑長設為 ∞。
完成後可得下圖右表，表中數字代表從 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 演算法」的步驟如下：
- 挑定一節點為始發節點 A，A 到所有節點的距離皆預設為 ∞。
- A 到 A 的路徑長為 0，比原本的 ∞ 短，因此將 A 到 A 的距離改為 0，並將 A 節點與 A 到 A 的路徑長資訊放進「priority queue」中。
- 依路徑長的數值小至大順序依序拜訪「priority queue」中的節點，檢查從 A 到該節點原有的距離，是否比從 A 節點沿本次路徑經過的距離還短。
- 若原有距離較短，則不變；若沿本次路徑經過的距離較短，則將 A 到該節點的路徑長與前一個節點資訊更新，並將該節點名稱與路徑長資訊放進「priority queue」中，「priority queue」中的節點順序固定依照路徑長由小到大排列。
- 重複 3.~4.，直到「priority queue」為空、每個節點都被拜訪過為止。
圖解「Dijkstra 演算法」過程範例如下，黃底節點代表目前所在節點、深棕底節點代表已經拜訪過的節點、黃邊為從目前所在節點離開可抵達的鄰居節點：
原圖，挑定始發節點為 A，A 至各節點路徑長皆預設為 ∞，「priority queue」為空。
A 到 A 節點的路徑長為 0，比原預設的 ∞ 短，因此將 A 到 A 路徑長改為 0，並將 A 節點放進「priority queue」中。
拜訪「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 節點為優先。
- 拜訪「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 節點為優先。
- 拜訪「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 節點為優先。
- 拜訪「priority queue」路徑長最短的 D 節點，從 D 出發可抵達 E 節點。
判斷 A 到 E 節點的路徑長：
因步驟 5. 所求從 A 到 E 節點路徑長為 6，實際從 A 經 B、D 到此的路徑長為 2+3+4=9，既有路徑較短，故 E 的前一個節點維持為 C、路徑長保持為 6，E 在「priority queue」中的路徑長也維持不變。
- 拜訪「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）」小結
- 左子節點必定先於右子節點。
- 根在左子節點之前先走過，稱為「preorder」。
- 根在兩子節點之間走過，稱為「inorder」。
- 根在走完兩子節點後才走過，稱為「postorder」。
小結
- 圖：表示物件之間關係，以「節點」表示物件、「邊」表示節點間關係。
- 簡單圖：邊無方向的圖。
- 有向圖：邊有方向的圖，可能為單向或雙向。
- 混合圖：包含有向邊與無向邊的圖。
- 加權圖：邊有「權重」的圖。
- 同構：圖的架構相同，僅外觀不同。
- 正則圖：每個節點同度。
- 完全圖：任兩節點間皆有一邊連結，若為有向圖，則所有的邊皆為雙向。
- 連通圖：沒有節點落單，若為有向圖，可再分為「弱連通圖」、「單連通圖」與「強連通圖」。
- 二分圖：節點可分為兩部分。
- 循環圖：可形成單環，若為有向圖，則所有邊的方向相同。
- 樹：無環的連通圖。
- 有根樹：可有一節點為「根」，除此之外另可有雙親節點、左右子節點、手足節點、堂表手足節點、葉、內部節點、祖先、子嗣、路徑、左右子樹構造，以及層、高度、深度、寬度、直徑等性質。
- 二元樹：任一雙親節點的子節點數量不超過 2 個。
- 二元滿樹：任一節點的子節點數量皆為 0 或 2。
- 完整二元樹：非最底層節點無空缺，最底層節點由左到右排列。
- 完美二元樹：所有內部節點都有 2 個子節點，且葉都在同層。
- 二元搜尋樹：任一子樹數值大小順序為「左子節點≥根≥右子節點」。
- 森林：無環、但可不連通的圖。
- 遍歷：拜訪圖中節點。
- 鄰接表：用無序列表表示節點間是否可互達。
- 鄰接矩陣：用矩陣表示節點間是否可互達，其乘冪代表走幾步可從某節點走到其他節點或回到原節點，稱為「可達性矩陣」。
- 歐拉路徑問題：節點可重複拜訪，邊都只走過一次，條件為起點跟終點都必接奇數條邊、中間節點都必接偶數條邊，或者全部節點都連接偶數條邊。
- 哈密頓路徑問題：節點只拜訪一次，邊可重複拜訪，屬於 NP 完全問題，目前只能用回溯法暴力解開。
- 中國郵遞員問題：所有邊都至少經過一次且可重複經過，無向圖是 P 問題、有向圖是 NP 完全問題。
- 旅行推銷員問題（TSP）：節點只拜訪一次，邊可重複拜訪，求最短路徑，屬於 NP 完全問題，目前只能用分支定界法暴力解開。
- 最短路徑問題：在加權圖中用總權重最小的方式從一節點移動到另一節點。
- Floyd–Warshall 演算法：求任兩節點間最短路徑，時間複雜度為 O(n³)。
- Dijkstra 演算法：求單緣最短路徑，以優先隊列輔助，不可用於有負邊的圖，時間複雜度為 O((|V|+|E|)·log|V|)。
- 隊列（queue）：類似排隊，先進先出。
- 堆疊（stack）：類似堆東西，後進先出。
- 寬度優先搜尋（BFS）：一層一層往外拜訪所有節點；用「queue」輔助實現。
- 深度優先搜尋（DFS）：逐一拜訪所有節點，遇到死胡同或拜訪過的節點時折返，最終回到原節點；用「stack」輔助實現。
- 樹的「寬度優先搜尋（BFS）」：從根開始一層一層往下走，每層內從左往右走。
- 前序遍歷（preorder）：對於樹中任一節點而言，遍歷順序為「根→左子節點→右子節點」。
- 中序遍歷（inorder）：對於樹中任一節點而言，遍歷順序為「左子節點→根→右子節點」。
- 後序遍歷（postorder）：對於樹中任一節點而言，遍歷順序為「左子節點→右子節點→根」。
