### 緣由

因為隨著一 Graph 的 vertices 個數增加，spanning tree 的個數呈指數成長，所以我們不可能透過一個一個確認 tree weight 來找出minimum spanning tree。

所幸 spanning tree 有兩個重要的 properties:

1. Cut Property
2. Exchange Property

可幫助我們迅速縮小尋找 MST 的範圍，也從這兩個 properties 衍伸出尋找 MST 的 algo：

1. Kruskal
2. Prim

*一些可用公式直接算 spanning tree 個數的特例：

### Properties

#### 一些 tree 本身的性質

1. n 個 node 的 tree，邊數必為 n-1
2.
- 拿掉 tree 的任何一個邊，會使 tree 變成兩棵更小的 tree
- 但拿掉 cycle 的任何一個邊，不會使原本 connected 的 graph 變成 disconnected

#### Cut Property


>Cut Property 告訴我們可以用 Greedy 的方式來 construct MST
>>藉由不斷從兩個沒有 connected 的區域間挑出 min weight edge，最後我們就會得到MST
>>
> 最後一行應為 $X \bigcup \{e\} \subseteq T'$

#### Exchange Property


> spanning tree 有比 Cut Property 更強的 property，即 Exchange Property
>> Exchange Property 意味著我們可以藉由一連串的 exchange 動作，將一個 spanning tree 變成一個MST

---

### Algo

#### Kruskal

##### code


##### 方法
init
- 將 edge weight 由小排到大
- $X = \emptyset$
- 將每個點視為 trivial tree（只有一個點，沒有任何邊的 tree）

接著每個 step 試圖依序把 lightest weight edge 放到 tree 中
- 如果挑到的 edge 兩端都在同個 tree 中
- discard (直接不挑這個 edge，因為會形成 cycle)
- 否則（一端在某棵 tree T，另一端在另一棵 tree T'）
- 把這個 edge 加到 A 中（會造成 T, T' merge 成一棵 tree）

:::warning
簡單來說，Kruskal 就是不斷找 weight 最小的 edge，只要不會產生 cycle，就加進 MST 中，直到挑了 $|V|-1$ 個邊。
:::

- Kruskal 建立 MST 的過程即把 $|V|$ 個 connected components，進行 $|V|-1$ 次 merge，等同在 $A$ 中加入 $|V|-1$ 個邊；形成一個 connected component，等同形成一棵 tree。

---
#### Prim

##### code


##### 方法

> 相對 Kruskal 是不斷 merge 很多 tree，Prim 從頭到尾都是對同一棵 tree 去成長，每次將一個點加入這個 tree 中。

- 須額外 maintain 一個 <font color = "green">(priority) Heap H</font>，紀錄和 S 中某個點相鄰，且還沒加進 S 的點，其連到 S 中點的 edge 最小值是多少。（有點拗口，建議看英文解釋或下面例子）

##### 例子

可對照 code 與下方我有按照 code 去 trace 整個過程



:::warning
簡單來說，Prim 建 MST 的過程就是不斷找目前的 tree 可以連出去的邊中 weight 最小的，直到挑了 $|V|-1$ 個邊。
:::

##### 特點

Prim 建 MST 的過程基本上和 Dijkstra 找single source shortest path 的方法差不多，只差在 heap 裡 maintain 的 key value

Heap 裡某個 node 的 value 代表的意義：

- Dijkstra: 從 source 到此 node 的「path」長
- Prim: 未在挑好的點，連到已經挑好的點，最小的「edge」 weight

> 畢竟 Dijkstra 是要找 shortest path，所以 Heap 中當然紀錄的是 path 長而非單一 edge weight。

---
#### Kruskal 對比 Prim

Review 一下 Tree 的性質：

只要滿足
1. undirected
2. connected
3. acyclic（沒有 cycle）

就是 tree


因此，我們要驗證一個 Graph 是否為 Tree 只需確認圖中三個條件
>→ 但實際上定理告訴我們，不用確認三個條件，只要這三個條件中任兩個滿足，第三個就會自動成立。

Kruskal 就是確保 2, 3
Prim 則是確保 1, 3

---

### Reference

[Harvard Lecture Notes](http://people.seas.harvard.edu/~cs125/fall15/lec2.pdf)
[Berkeley Lecture Notes](https://people.eecs.berkeley.edu/~vazirani/sp04/notes/greedy)