# 最小生成樹
> 上一篇文章　[圖論基礎概念](https://hackmd.io/@iDoNotWantToCoding/B1-JtywhJl)
> 下一篇文章　[堆疊/佇列介紹/題目介紹](https://hackmd.io/xDDGU8IKTGuALGY_SdFa-Q)、[分治演算法介紹](https://hackmd.io/mHF6PhkFTzmx0CQvuLdxng)
> 先備知識　　無
> 延伸閱讀　　無
---

Minimum Spanning Tree (MST）是圖論和計算機科學中的一個基本概念。
它屬於一個無向圖的子集，連接了所有的頂點，並且具有可能的最小總邊權重。

## <font size=6>Prim’s algorithm</font><br>

### 概述
Prim’s algorithm 需要先隨機選取一個點作為起始點，再依據此點周圍權重最小的邊區尋找下一個點，並且取的邊不能使樹形成Cycle，重複上述步驟最後就會得到最小生成樹。

### 範例：在無向圖中找出最小生成樹
>步驟:初始化→選最小邊→得到MST
### 步驟一 : 初始化
首先先找一個點作為起始點(可依題目要求設定起始點)，這題我們先選`A`作為我們的起始點。

min_heap = [(0, start, None)]
visited = set()
mst = []

>從 `start`（例如 'A'）出發
加入一條假邊`(0, 'A', None)`作為起點
`visited` 是已經加入生成樹的節點(目前是空的)
`min_heap` 儲存所有候選邊，每次都取最小的

### 步驟二：從起點開始擴展

weight, u, from_node = heapq.heappop(min_heap)

>從 `min_heap` 中取出目前權重最小的邊
第一次會取出 `(0, 'A', None)`，表示從自己開始

### 步驟三：加入節點並記錄邊

if u in visited: #檢查是否成環
    continue

visited.add(u)

if from_node is not None:
    mst.append((from_node, u, weight))

>如果這個節點已經訪問過，會成環 ➜ continue，重新回到步驟二
>如果節點不存在`visited`，則把它加進已訪問集合`visited`
>如果 from_node 存在（不是起點`None`），就記錄這條邊進入`mst`中

### 步驟四：探索鄰邊，加入候選邊

for edge_weight, v in self.graph[u]:
    if v not in visited:
        heapq.heappush(min_heap, (edge_weight, v, u))

>掃描剛剛加入的節點`u`所有鄰邊
把尚未訪問過的邊(從`u`出發的邊)，丟進 `min_heap`
這些就是下一輪可能延伸的邊

以上面的圖為例:

跑第一次迴圈時，因為min_heap中還沒有東西
| 跑第一次迴圈 |
| -------- |
| 候選邊更新為`[(1, A, B), (7, A, C), (5, A, E), (10, A, D)] `← 所有從 A 出發的邊 |

跑第二次迴圈時，選中 `A -- B`(最便宜的邊)加進 MST，並從`min_heap`中去除`(1, A, B)`

| 跑第二次迴圈 |
| -------- |
| 候選邊更新為`[(3, B, C), (7, A, C), (5, A, E), (10, A, D)]` ← 加入所有從 B 出發的邊 |

所以跑第三次迴圈時，會選中`B -- C`加進 MST，並從`min_heap`中去除`(3, B, C)，再加入所有從C出發的邊

### 步驟五：進入迴圈，重複擴展
每次都會：
1. 拿出最小邊 ➜ 判斷是否能用（會不會成環）
2. 如果可以，就加入邊與節點
3. 然後掃鄰邊，加進候選邊清單

直到所有節點都加入為止。
當`len(visited) = len(self.graph)`時代表所有節點已經被訪問過，所以結束迴圈，得到MST
:::success
Prim’s algorithm 是從所有已加入的節點中所有可延伸出去的邊中尋找`Weight`最小的邊，最後形成MST
:::
:::danger
不是從最後加入的節點中尋找最便宜的邊
:::
### 完整程式碼

:::spoiler 什麼是`heapq`（點我展開）
`heapq` 是 Python 內建模組，提供堆積（heap）資料結構的操作方法
`heappush(heap, item)`：把 item 丟進堆中，會自動排好順序
`heappop(heap)`：從堆中「取出最小值」
:::

import heapq

class PrimGraph:
    def __init__(self):
        self.graph = {}  # 使用鄰接表表示圖：{'A': [(1, 'B'), (5, 'E')]}

    def add_edge(self, u, v, w):
        # 為無向圖，雙向加邊
        self.graph.setdefault(u, []).append((w, v))
        self.graph.setdefault(v, []).append((w, u))

    def prim_mst(self, start):
        visited = set()  # 紀錄已經加入 MST 的節點
        min_heap = [(0, start, None)]  # 儲存候選邊 (邊的權重, 當前節點, 來源節點)
        mst = []  # 最小生成樹的邊集合

        while min_heap and len(visited) < len(self.graph):
            weight, u, from_node = heapq.heappop(min_heap)

            # 若該節點已訪問過，表示這條邊會成環，跳過
            if u in visited:
                continue

            visited.add(u)

            # 如果不是起點，加入這條邊到最小生成樹
            if from_node is not None:
                mst.append((from_node, u, weight))

            # 掃描此節點的所有鄰居，加入新的候選邊
            for edge_weight, v in self.graph[u]:
                if v not in visited:
                    heapq.heappush(min_heap, (edge_weight, v, u))

        return mst

g = PrimGraph()
g.add_edge('A', 'B', 1)
g.add_edge('A', 'C', 7)
g.add_edge('A', 'D', 10)
g.add_edge('A', 'E', 5)
g.add_edge('B', 'C', 3)
g.add_edge('C', 'D', 4)
g.add_edge('D', 'E', 2)

mst = g.prim_mst('A') #起點為A

print("最小生成樹的邊：")
for u, v, w in mst:
    print(f"{u} -- {v} == {w}")

> **Output**
> ```
>最小生成樹的邊：
>A -- B == 1
>B -- C == 3
>C -- D == 4
>D -- E == 2
> ```

## <font size=6>Kruskal’s algorithm</font><br>
### 概述
Prim’s algorithm跟Kruskal’s Algorithm最不一樣的地方是，Prim’s 需要先有一個起始點，而Kruskal’s 是直接找最小邊(Edge)。

Kruskal’s algorithm首先將所有邊(edge)及邊的權重由小到大排序，然後依序添加這些權重小的邊，在添加的過程中使用並查集檢查是否形成環，如形成環則將其拋棄，否則繼續添加邊直到所有頂點(node)皆連接在一起。
### 範例：在無向圖中找出最小生成樹
### 依權重及優先權排序
首先，先找出在無向圖中所的的邊。
接下來，將所有邊依照權重排序。
<font color="#F00">如果出現權重相同權重的情況須依題目要求排序(如：依照英文字母順序排序)</font>
> **範例程式碼**
> - 其中`u`和`v`分別代表的是該邊的起始頂點以及另一個結束的頂點，`W`則代表該邊之權重。
> ```python=9
> def add_edge(self, u, v, w):
> self.edges.append((w, u, v)) # 儲存邊（依照權重排序）
> self.edges.sort() # 每次加入邊時自動排序
> ```
### 依序加入並檢查是否形成環
使用並查集檢查是否形成邊，假設一開始所有頂點皆沒有連接任何邊，因此所有點都屬於自己的集合，當點有邊連接時，代表他們屬於同一集合，因此使用並查集判斷，判斷他們是否已經為同一集合。
> **範例程式碼**
> :::success
> - `find(parent, u)`會返回`u`所屬集合的代表根節點
> - `find(parent, v)`會返回`v`所屬集合的代表根節點
> - 如果`find(parent, u) != find(parent, v)`，代表`u`和`v`在不同集合內，如果加入`(u, v)`則不會形成環。
> :::
> :::danger
> - 如果`find(parent, u) == find(parent, v)`，代表`u`和`v`已經在同一集合內，如果加入`(u, v)`則會形成環。
> :::
> ```python=37
> root_u = self.find(parent, u)
> root_v = self.find(parent, v)
>
> if root_u != root_v: # 只有當 u 和 v 不在同一集合時才加入
> mst.append((u, v, w))
> self.union(parent, rank, root_u, root_v)
> ```
### 加入MST圖中
當透過並查集檢查後，如果沒有形成環，就使用`union`將邊加入MST圖中。
> **範例程式碼**
> - 合併方式：
> -- 將較矮的樹合併至較高的樹。
> -- 如果高度相同，選擇`x`為根進行合併，合併之後將`rank[x]`+1，以確保之
> 後的合併資訊正確。
> ```python=19
> def union(self, parent, rank, x, y):
> root_x = self.find(parent, x)
> root_y = self.find(parent, y)
>
> if rank[root_x] < rank[root_y]:
> parent[root_x] = root_y
> elif rank[root_x] > rank[root_y]:
> parent[root_y] = root_x
> else:
> parent[root_y] = root_x
> rank[root_x] += 1
> ```
### 成果
結束後所產出的最小生成樹如下：

### 完整程式碼

class Graph:
    def __init__(self, vertices):
        self.V = len(vertices)  # 頂點數
        self.nodes = list(vertices)  # 儲存字母頂點
        # 建立字母->數字映射
        self.node_index = {node: i for i, node in enumerate(vertices)} 
        self.edges = []  # 儲存邊
    
    def add_edge(self, u, v, w):
        # 轉換為數字索引
        self.edges.append((w, self.node_index[u], self.node_index[v]))  
        self.edges.sort()
    
    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])
    
    def union(self, parent, rank, x, y):
        root_x = self.find(parent, x)
        root_y = self.find(parent, y)
        
        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1
    
    def kruskal_mst(self):
        parent = list(range(self.V))
        rank = [0] * self.V
        mst = []

        for w, u, v in self.edges:
            root_u = self.find(parent, u)
            root_v = self.find(parent, v)

            if root_u != root_v:
                mst.append((self.nodes[u], self.nodes[v], w))  # 轉換回字母
                self.union(parent, rank, root_u, root_v)

        return mst

# 測試範例
graph = Graph(['A', 'B', 'C', 'D', 'E'])
graph.add_edge('A', 'B', 1)
graph.add_edge('A', 'C', 7)
graph.add_edge('A', 'D', 10)
graph.add_edge('B', 'C', 3)
graph.add_edge('C', 'D', 4)
graph.add_edge('D', 'E', 2)

mst = graph.kruskal_mst()
print("最小生成樹的邊：")
for u, v, w in mst:
    print(f"{u} -- {v} == {w}")

:::spoiler **註**（點我展開）
`__init__(self, vertices)`：初始化最小生成樹及其資訊
`add_edge(self, u, v, w)`：將各個邊輸入並排序
`find(self, parent, i)`：找出該點所有的根節點集合
`union(self, parent, rank, x, y)`：並查集判斷是否形成環，如無則合併
`kruskal_mst(self)`：將圖進行Kruskal's Algorithm處理
:::
> **Output**
> ```
> 最小生成樹的邊：
> A -- B == 1
> D -- E == 2
> B -- C == 3
> C -- D == 4
> ```

---
> 上一篇文章　[圖論基礎概念](https://hackmd.io/@iDoNotWantToCoding/B1-JtywhJl)
> 下一篇文章　[堆疊/佇列介紹/題目介紹](https://hackmd.io/xDDGU8IKTGuALGY_SdFa-Q)、[分治演算法介紹](https://hackmd.io/mHF6PhkFTzmx0CQvuLdxng)
> 先備知識　　無
> 延伸閱讀　　無