演算法與資料結構：圖和樹的定義 | 遍歷 | 最小生成樹 | 堆積排序 | Stack & Queue

上次我們提到了演算法（algorithm），它是一種解決問題的方式。但演算法只是資料結構與演算法（Data Structures and Algorithms, DSA）這個領域的一部分。今天，我們要進一步探索這個主題，了解它的核心概念。

** 10/14新增堆積排序

什麼是資料結構與演算法呢？簡單來說，資料結構是用來組織和存儲資料的方式，而演算法則是用來處理這些資料的步驟。這兩者緊密結合，讓我們能夠有效率地解決各種計算問題。

接下來，我們會介紹一些基本概念，例如圖（graph）和樹（tree）的定義，如何進行遍歷（traversal），什麼是最小生成樹（minimum spanning tree），還有日常應用中的堆疊（stack）與佇列（queue）。

本文的資料與圖片參考以下兩個來源，後續若有程式碼會更新文章。

https://www.geeksforgeeks.org/

拉爾夫的技術隨筆－圖論

溫故知新：

編譯四階段| 直譯語言 | 陣列概念 | 除錯三妙招

為什麼要學習圖、樹，圖和樹又有什麼不同？

為什麼要學習圖和樹？

學習圖和樹這些資料結構非常重要，因為它們在真實世界中有廣泛的應用：

1. 圖（Graph）：
2. • 社交網路：臉書（Facebook）或 Instagram 的使用者和他們的好友之間的連結就是一個典型的圖。節點代表使用者，邊代表好友關係。
   • 地圖與導航：像是 Google Maps 這樣的應用程式會將城市中的地點當作節點，將道路當作邊，並用權重來表示路程時間或距離，找到最短路徑。
2. 樹（Tree）：
3. • 資料搜尋：像是二元搜尋樹（Binary Search Tree, BST）能夠有效地進行資料搜尋、插入與刪除操作，這是許多演算法的基礎。
   • 階層式結構：檔案系統的資料夾結構、公司內的組織圖、分類系統等，這些都是樹的應用，讓我們能夠以直觀的方式呈現資料的層次關係。

圖與樹的定義

圖（Graph） 是由以下兩個部分組成的資料結構：

• 頂點（Vertices/Nodes）：節點，代表資料點。
• 邊（Edges/Connections）：連接各節點的線，表示節點之間的關係或連結。

圖的邊可以有不同的特性：

• 有向圖（Directed Graph）：邊有方向性，連接的節點有「起點」與「終點」，通常會用箭頭表示。
• 無向圖（Undirected Graph）：邊沒有方向性，表示節點之間是相互連接的，沒有明確的起點或終點。
• 加權圖（Weighted Graph）：邊帶有數值，這個數值可以表示兩個節點之間的成本、距離或其他特徵。
• 無加權圖（Unweighted Graph）：邊不帶有任何數值。

下圖是一個有向且加權的圖，每條邊都有箭頭來表示方向，並且邊上有數字表示「權重」，例如路徑的距離或花費的成本。

樹（Tree）是圖的一種，定義比圖嚴格。

1. 不會形成環：樹中的節點（Node）和邊（Edge）之間不會形成封閉的循環路徑。換句話說，從任何一個節點出發，不會走回自己。
2. 有唯一的走法：在樹中，從一個節點到另一個節點只有唯一的一條路徑。
3. 層級結構：樹通常有一個稱為「根節點（Root Node）」的頂點，其他的節點依據層級往下排列，就像檔案或公司組織圖一樣，從上到下形成層次分明的結構。

樹的實際應用如檔案系統，組織系統

下圖是樹的完整組織架構節錄，想要更進階了解的讀者可以參考：

拉爾夫的技術隨筆－圖論

1. 根節點（root node）：樹中的最頂層節點
2. 雙親節點（parent node）：任兩層相連的節點中，較靠近「根」者，如下圖的 D 點。
3. 子節點（child node / children）：任兩層相連的節點中，較遠離「根」者，可再依其所在雙親節點的相對位置分為「左子節點（left child）」及「右子節點（right child）」。
4. 手足節點／兄弟節點（sibling node）：所有共享同一雙親節點的同層節點。
5. 葉（leaf / leaves）：沒有任何子節點的節點，
6. 路徑（path）：連接任兩節點之間所有的邊與節點。
7. 子樹（subtree）：以根以外的節點為新節點形成的小樹，可再依其所在新的根的相對位置分為「左子樹（left subtree）」及「右子樹（right subtree）」

樹的型態：二元樹（Binary Tree）

樹的種類超級多，光是二元樹就有各種不同的分支，首先介紹二元樹的長相。每個節點都有不超過 2 個的分支，以下僅介紹部分的二元樹：

更多樹的型態介紹可以參考：拉爾夫筆記

樹的遍歷（Tree Traversal）

當我們建立好樹的結構後，接下來最重要的問題就是：如何找到我們想要的答案？在樹的世界裡，目標節點的搜尋可不是隨便找找就能找到的，這就涉及到樹的遍歷。

遍歷的意思

遍歷就是一種系統化的搜尋方式，主要有兩大類模式：

Breadth First Search (BFS) – 寬度優先搜尋：

BFS 是一種優先按層級的搜尋方式，會先從樹的最上層開始，逐層搜尋每一層的所有節點，確保每個節點都被拜訪過，像是一層一層地探索整棵樹。

Depth First Search (DFS) – 深度優先搜尋：

DFS 是一種優先深入某個路徑的搜尋方式，可以有三種常見遍歷方式：先序、中序、後序。它通常會沿著樹的某一路徑深入到底，然後再回頭尋找其他路徑。

以這顆樹來說，要怎麼讀過所有的節點呢？

前序遍歷（Pre-order Traversal）

在前序遍歷中，我們的策略是先讀取根節點，然後依次深入左子樹，最後再到右子樹。具體來說，對於這棵樹，我們會先讀取左邊的節點 R、A、C、D，然後再轉到右邊的 B、E、F、G。這種遍歷方式特別適合用於需要先處理根節點的情況，像是構思或建立樹的結構。

如果你想更深入了解先序遍歷的運作方式，可以參考這裡的詳細動畫：W3Schools - Pre-order Traversal。

中序遍歷（In-order Traversal）

在中序遍歷中，我們會從最下面的葉子節點開始，優先讀取左邊的分支。接著，依據之前的示意圖，In-order Traversal 的路徑為：C、A、D、R、E、B、G、F。這種方式讓我們可以在讀取樹的節點時，先處理左子樹，再處理根節點，最後處理右子樹。

後序遍歷（Post-order Traversal）

後序遍歷同樣是深度優先搜尋（Depth First Search, DFS）的一種方式。在這種遍歷中，我們會先讀取左子樹，然後是右子樹，最後才是根節點。後序遍歷特別適合用於刪除整棵樹，因為它確保在刪除根節點之前，已經處理了所有的子節點。

小結

• 前序遍歷（Pre-order Traversal）：根 -> 左 -> 右
• 中序遍歷（In-order Traversal）：左 -> 根 -> 右
• 後序遍歷（Post-order Traversal）：左 -> 右 -> 根

最小生成樹（Minimum Spanning Tree, MST）

介紹完搜尋結點的方式，接下來介紹一個圖論 （Graph）的重要觀念，最小生成樹。最小生成樹走完圖中所有的節點。最小生成樹需要符合以下特性：

1. 連接所有點：每個點都要互相連接，不漏掉任何一個。
2. 沒有環：選擇的邊不會形成迴圈（即圖中沒有某條邊讓你繞回原來的地方）。
3. 總權重最小：你選擇的邊的權重和要是所有可能情況中的最小值，意思就是說你找到了一條連接所有點的最省錢、最短或最節省資源的路。

比喻說明

想像一下，你是市長，想要鋪設道路連接5個城市，你有幾種不同的路徑可以選擇，每條路徑的建造成本（即邊的權重）不同。為了節省預算，你需要選出能連接所有城市的最便宜的道路組合。這樣做出來的方案，就是一棵最小生成樹。實際上最小生成樹的應用可以是，電腦網絡建設、交通網路規劃、電力網。

常見的最小生成樹演算法

為了找到最小生成樹，有一些經典的演算法，他們都是貪婪演算法的延伸：

1. Kruskal 演算法：每次選擇權重最小的邊，並避免形成環，直到所有的點都連接起來。
2. Prim 演算法：從任一個點開始，不斷選擇連接到樹上且權重最小的邊，直到所有點都被連接。

兩者比較

• Kruskal 演算法：可以處理不連通的圖，因為它是以邊為主，會找到最少生成樹，也可以形成最小生成森林 Minimum Spanning Forest。
• Prim 演算法：需要圖是連通的，因為它是從單一節點擴展，無法自動跳到其他不連通的節點。

Kruskal 演算法：

1. 先計算每個點到點的距離，再從最短距離的兩個點開始。
2. 分別是 C - E 的 2，E-D的 3 和A-B 的 4，但下一個是 5 沒有辦法連，因為會變成一個環。

3. 所以改走 距離為 6 的E-G，再下一步又發現是 7 不能走，所以再去找比 7 大 的邊，再把所有的邊確認完畢，刪除不可能的選項就是這張圖的最少生成樹了。

最短路徑分析 Dijkstra's Algorithm

1. 將起點設為 0 其他設無限大 (Inf)。
2. 選擇未讀過的最短距離節點。在這個例子選擇 E。
3. 更新鄰近節點的距離：以下圖來看，走到 E 時就要把 2 填入 E。
4. 標記節點為已讀過。
5. 重複步驟 2 到 4，直到所有結點都讀過為止。

堆積排序（Heap Sort） : 樹的延伸排序

堆積排序是基於二元堆積（Binary Heap）資料結構的排序演算法。它的運作方式與選擇排序有點像，都是透過每次選擇最大值（或最小值），再跟未排序的數列中最左邊（或最右邊替換）。但由於他有二元樹的特性，所以時間複雜度會比選擇排序來的低。

• Binary heap 是一個完全二元樹 (complete binary tree)，完全樹的意思是除了最後一層外每一層都填滿，最後一層必須由左至右填入。

時間複雜度

堆積排序的時間複雜度為 O(nlogｎ)，其中 O(logn) 是維持堆的結構所需的時間，而整個排序過程需要進行 n 次操作。因此，堆積排序比選擇排序更有效率，特別是在處理量資料的時候。

堆積排序的過程：

假設我的目標是，由小排到大，最頂端的數字最小。

1. 先將待排序的陣列轉換為一個「最大堆（Max Heap）」或「最小堆（Min Heap）」。** 要最頂端的數字最小，但是一開始我要先把較大的數字換到上面。（詳見下圖）。
2. 每次將堆頂元素（最大或最小值）取出，並將其與當前未排序部分（last element of the heap）的末端元素交換。
3. 重新調整堆，維持最大堆或是最小堆。
4. 重複這個過程，直到所有元素排序完成。

看起來有夠複雜，我們來看圖示：

得到每一層節點都比下一層大

把頂端最大值換到最底層：

這裡跟選擇排序有點類似，當換過之後，就不用再處理這個節點。

上圖已經被破壞了，我們要想辦法維持它是最大堆（父母節點比子節點大）的狀態，所以要繼續進行第三步。

維持成最大堆後，再去最底層跟最小值換，這時候 9 和 10 已經被排序好了。

但是跟第三步一樣，已經不是最大堆或是最小堆了，所以繼續交換使其為最大堆。

已經是最大堆了，那我們就把最頂端跟最底層的最小值交換。

複習各種排序

演算法 | 選擇排序 | 氣泡排序 | 合併排序 | 遞迴

堆疊（Stack）佇列（Queue）

堆疊的運作方式是「後進先出」（Last In, First Out，LIFO），也就是最後放入堆疊的元素會最先被取出。想像一個裝滿書的盒子，你最後放進去的書會是最先拿出來的。

堆疊的方式如下圖，後進後出。

當輸入 pop() 最上面的會先被拿掉

以陣列顯示的話，輸入 pop() 會變成什麼呢？

而排序的方式則是先進先出。First in First out，所以當我按 dequeue() 刪除時，會先將第一個踢出去。

DSA 相關問題補充：

旅行銷售員問題（The Traveling Salesman Problem, TSP）

給定一系列城市及任兩個城市間的距離，找出造訪每個城市一次並回到起始城市的最短路線

旅行銷售員問題是一個經典的組合最佳化問題，其目標是找到一條最短路徑，讓業務員可以在多個城市間巡迴，並最終回到起點。這個問題非常實際，尤其在物流和供應鏈管理中，但時間複雜度非常高，為 O(n!)。

為什麼是 O(n!)？

對於 n 個城市，旅行者必須考慮所有可能的城市排列。舉例來說，若有 3 個城市（例如 A、B 和 C），那麼所有的路徑排列如下：

• A -> B -> C -> A
• A -> C -> B -> A
• B -> A -> C -> B
• B -> C -> A -> B
• C -> A -> B -> C
• C -> B -> A -> C

這些排列的數量是 n!（n 的階乘），即 3!=3×2×1=6。若有 10 個城市，則計算量會更驚人，因為 10!=3,628,800。

樹狀圖解釋

為了更直觀地理解旅行銷售員問題，可以用樹狀圖來表示所有可能的路徑：

1. 第一層：從城市 1（例如 A）出發。
2. 第二層：接下來可以到城市 2（B）或城市 3（C），所以在第二層會畫出兩條分支，分別是 A -> B 和 A -> C。
3. 第三層：如果選擇了 A -> B，則第三層會有 B -> C，然後再回到 A。如果選擇了 A -> C，則第三層會有 C -> B，然後回到 A。

這樣的樹狀圖會逐步展開，直到所有可能的排列都被列出來。最終，必須計算每條路徑的距離，並選擇最短的那一條。

詳細影片解說

4.7 Traveling Salesperson Problem - Dynamic Programming

感謝你看到這裡，有任何問題，歡迎指教~