# Minimum Spanning Tree 最小生成樹
### Wiring Problem 佈線問題

* 問題：
> 電路有一堆針腳還有電線，一條電線只能連接兩個針腳，成本是 $w(u,v)$

* 目標：安排足夠但不多餘的電線使得每個針腳都連通，總成本最小

* Modeling Problem：
* 把問題建模成一張無向的連通圖
* $G=(V,E)$
* $V$：所有針腳
* $E$：每條佈線選項 (edge)
* 找到一個 $T\subseteq E$ 使得：
* $T$ 是一棵最小生成樹
#
### Minimum Spanning Tree 最小生成樹
> 在所有生成樹中權重最小的那一個

* 定義：
* 可能有多餘一個最小生成樹
* 一定沒有環
* 任何生成樹都有且只有 $|V|-1$ 條邊
#
### Growing a Minimum Spanning Tree

* 建議一個 `edge` 的集合 $A$

* 不斷加入邊同時迴圈不變量 (每次迭代前 $A$ 都是某棵MST的子集)

* 只加入 `safe edge`
* `safe edge` 的定義是若 $A$ 是某個MST的子集，加入 $(u,v)$ 後 $A$ 依舊是某棵MST的子集

* 通用虛擬碼：
#
### Loop Invariant 迴圈不變量

* Initialization 初始化：
* 第一行後 $A$ 是空集合，當然是某棵MST的子集

* Maintenance 維持：
* 2~4行每次只會加入 `safe edge` 所以不變量一直成立

* Termination 終止：
* 當演算法結束時，加入 $A$ 當中的邊都在某棵MST內，回傳的 $A$ 必然就是一棵MST
#
### Disjoint-set Data Structures
> 維護一組動態變化的集合，裡面的元素是彼此不重疊的集合的資料結構。

* MAKE-SET($x$)
* 建立一個新集合 $S_i=\{x\}$ 並加入集合族 $S$

* UNION($x,y$)
* 若 $x$ 在集合 $S_x$ , $y$ 在集合 $S_y$ , 把兩個集合合併後銷毀兩個原先集合。

* FIND-SET($x$)
* 回傳包含 $x$ 的那個集合的代表元
#
### Kruskal's Algorithm

* 一開始每個頂點都是獨立的component

* 將所有權種邊排序好後選擇權重最小的那一條，合併兩個component

* 反覆執行這件事情

* 使用 `disjoint-set` 去判斷是否不同component

* 時間複雜度：$O(E\log V)$

* 虛擬碼：
#
### Prim's Algorithm

* 從源頭(root)開始維持一棵樹

* 從任意節點 $r$ 開始

* 從在樹中的節點 $V_A$ 中找到一條權重最低的候選邊把新頂點拉進來

* 使用 `Priority Queue` $Q$ 存還沒進入MST的點

* $key[v]$ 目前已知把 $v$ 連接到MST中最便宜成本

* $\pi[v]$ $v$ 在MST中的父節點

* 時間複雜度：$O(E\log V)$

* 虛擬碼