---
title: Greedy Algorithm / Spanning Tree
tags: 演算法(交大OCW)
---
# Spanning Tree
第四台在拉線的時候，一定是從現有的線路拉線到還沒拉線的地方...
## 輸入
一個無方向性 G(V,E)，每條 E 的權重均 ≧ 0
- 去找出一個 E 的集合，使得權重加起來最小
- 並且所有的點都有連到 (is connected)
>可以回去複習 Connected 的定義
## 輸出
我要找到一個 E 的集合，這個集合可以把所有的 V 連起來
同時這個 E 的集合所花的錢(權重)是最少的
1. 根據定義，他一定是 Connected
2. 那他有沒有環？
- 假設他有環。那我就把其中一個 E 給拔掉，那他依舊是 Connected
- 因此這依舊符合我要找的結果
- 可是我既然都拔掉了，代表權重總和又變得更小，代表拔掉後的才是最佳解
- 因此，權重最小的一定不會是環，因為這個環一定可以再拆
因為得到的集合是 Connected，且不是環，所以是一顆 Tree
所以這個問題才被叫做 Spanning Tree 而不是 Spanning Graph
---
:::info
Minimal Spanning Tree = MST
:::
---
# Joseph B. Kruskal 1956
```c
1. 建立一個已經選好的集合 T = {}，一開始是空集合
2. 每次從 G 的 E 當中挑權重最小的出來，檢查跟已經選好的集合 T 會不會形成環
3. 不會的話就塞進已經選好的集合，會的話就跳過他挑下一條
```
下面這張圖，目前選到{B,C}這條，但是因為它會跟已經選好的形成環，所以就跳過他
最後就會得到這棵樹
:::warning
這就很像把很多棵小樹併成一棵大樹
:::
# Robert C. Prim 1957
思路跟 Kruskal 不一樣
```c
1. 由於最後一定要連接所有點，所以一開始就先隨便挑一個點
2. 每次從已經選好的所有點去看，看哪條 E 的花費最少，就選那條 E，以及與之相連的 node
```
下圖就是從 D 點出發，將 D 塞入已選好的點
往外看出去發現上面的路比較便宜，所以就走上面，並把 D 塞入已選好的點
此時選好的點有 2 個，所以就從 A 跟 D 看出去，哪條 E 比較便宜
發現是下面 {D,F} 那條，於是就把 F 塞入已選好的點
最後一樣可以得到
:::warning
跟 Kruskal 的差異在於，從頭到尾都維持一棵樹
:::
# Reverse Delete
:::info
整個逆向操作起來，用拔的，把不需要的拔掉
因為一棵 Tree 只有 n-1 個 E，所以拔到剩 n-1 個 E 就好
每次就挑最貴的 E 下手。不過拔的時候要注意不能讓 Tree 變成兩半
:::
---
# 總結
- Reverse Delete 由於在檢查會不會形成兩半的地方比較複雜
所以實際應用上最常用的還是前兩種演算法
- 其實還有更多種演算法，但這些演算法都會是對的，是基於**兩個重要的性質**
# Cut Property
:::info
甚麼情況下加入的 E 會是 「安全的」？
:::
為了方便，假設所有 E 的花費不一樣
>也可以推廣至 E 有一樣的花費
## Lemma
:::warning
把原本的 G 砍成兩半，這當中必定會砍到一些 E
在這些 E 當中，花費最小的 E ，一定會是 MST 的其中一條 E
:::
證明方法就是，不包含那個花費最小 E 的 Tree，總花費一定比較高
為了方便說明，此處叫那個花費最小 E 為 e
### 證明 Exchange arguments (?
假設有一棵 Spanning Tree，我把這棵樹包含的 E 的集合叫做 T，並且 T 不包含 e
上面有說 e 是原本的 G 被砍成兩半後，會被砍到的 E 的其中一條
換句話說就是，連接這兩半的 E 當中， e 是其中一條
而 T 不包含 e ，那他一定至少包含其中的另外一條 E，不然全部點就會斷開
此處叫該條 E 為 f
那麼很直覺的，我把 T 的 f 換成 e ，不就得到總花費更便宜的 T 了嗎
於是 Exchange argument 證明就成立了...
才怪
:::danger
雖然總花費變少了，但是把 f 換成 e，會有斷成兩半的可能
:::
像下圖，假設 S 就是原先被砍成兩半的其中一半，e 是花費最小的 E
有有一棵樹的 E 的集合 T ，他不包含 e ，但是包含 e^'^ 跟 f
這種情況，把 f 換成 e 的話，h 這個 node 就會被孤立
:::success
但是上面的大致思路是對的，只要修改一些地方就好
:::
## 證明 Exchange arguments
### 不損害 Quality
假設有一棵 Spanning Tree，我把這棵樹包含的 E 的集合叫做 T ，並且 T 不包含 e
這裡將原先 e 連接的兩點為 v 跟 w
**由於 Tree 是 Connected，所以一定存在一條 P 可以從 v 到達 w**
而且這條 P 一定包含原本的 G 被砍成兩半後，會被砍到的 E 的其中一條
>不包含的話，他又不包含 e ，那不就是砍成兩半嗎
這裡將連接那兩半的 E 為 e^'^，連接的兩點叫 v^'^ 跟 w^'^
圖示如下
此時如果把 e 給黏回 T ，那這樣 P + {e} 就會變成一個環
這時候把 e^'^ 給拔掉，v^'^ 跟 w^'^ 依舊可以透過 e 相連
也就是說，把 e^'^ 拔掉換成 e 並不會損毀 Connected 的性質
$$
T^{'} = T - \{e^{'}\} + \{e\}\ \ , (V,T^{'}) 依舊是一棵樹
$$
### 有著更好的解
由於 e 的花費比 e^'^ 小，所以替換後的樹總花費更小
---
:::info
- 在看投影片時，因為一直沒注意到 T 是指 Edge 的集合，就一直在納悶 (V,T) 到底是甚麼，後來才看到 T 是指 E 的集合
所以 (V,T) 是指一個 Graph ，也就是這裡要的 Tree
- Kruskal 跟 Prim 兩者就是基於 Cut Property，才可以安全的加入 E
:::
:::danger
這個例子是在告訴我們證明的時候除了說明 Greedy 得到的解更好
更不能忘記替換的過程不可以損壞原本解的Quality
:::
---
# Cycle Property
:::info
甚麼情況下可以「安全地」拔掉 E？
:::
## Lemma
:::warning
將原本的 G 中存在的某個 Cycle 叫做 C，這個 C 所包含的 E 中
最貴的一定不在 MST 中
:::
:::success
老師說證明跟 Cut Property 很像，這裡就不證了
原則就跟上面的一樣
:::
---
# Implementation
因為 Prim 的本質是跟 Dijkstra 一樣，所以也是用 Min Priority Queue
而 Kruskal 則是用到 Set 這個資料結構，以及他的功能 Union Find
# Prim
只跟 Dijkstra 的演算法差在第四行，以及 d value 的設計
## Pseudo Code
```c
// S：the set of explored nodes
// for each u in S, we store a shortest distance d(u) (tree edge)
Dijkstra(G,L)
1. init S = {s}, d(s)=0
2. while S ≠ V do
3. select a node v not in S with at least one edge from S for which
```
$$
4.\ d'(v)=min_{\theta=(u,v):u\in S}L_{\theta}\
$$
```c
5. add v to S and define d(v)=d'(v)
```
下面是原本 Dijkstra 的第四行
$$
4.\ d'(v)=min_{\theta=(u,v):u\in S}\{d(u)+L_{\theta}\}
$$
只差在 Dijkstra 需要考慮總和起來最小，而 Prim 只要選向外延伸花費最小的就好
### d value
Dijkstra 的 d value 是 shortest path distance from s to u
也就是儲存到達該點的最短距離
Prim 則只要存 shortest distance，也就是該點所含有的 E 中，長度最短的
每次把某個點加入 S 後，跟 Dijkstra 一樣，就要更新 d value，不過是更新成第二短的 E，因為原先最短的 E 已經被用掉了
在 Dijkstra 中 queue 是存放未放入 S 的點；但是在 Prim 中 queue 存放的就是 S ，每次都是從已經放入 S 的點去找
---
# Kruskal
```c
Kruskal(G,c)
1. {e1,e2,e3...em} sort edged in ascendimg order of their costs
2. T = {}
3. for each ei=(u,v)do
4. if( u and v are not connected by edges in T) then //different sub tree
5. T = T + {ei}//merge these two corresponding subtree
```
「u and v are not connected by edges in T」，就是要避免 Cycle
# Union-Find
:::info
是一種用來表示 Disjoint Sets 的 Data Structure
裡面的每個元素是不重複的；每個 Set 都有一個「代表」Representative
:::
每棵小樹就是一棵 Disjoint Set
## 功能
- MakeUnionFind(S)：
- 將每個 S 的元素初始化成一個 Set
- Find(u)：
- 找出包含 u 的 Set 的 Representative
- Union(A,B)：
- 將 A, B 兩個 Set 合併起來
## Implementaion
這裡是以 Tree 的方式實作 Union-Find，其中 Root 就是 Representative
R. E. Tarjan 他們有發展一些技巧，讓 Union-Find 的功能可以變得很快速
- Union by Rank
- 也就是根據兩個 Set 的 Rank 進行 Union
- 把較小的樹，也就是 Rank 較小的，併到 Rank 較大的
- Path Compression
- 對於一個點，每做過一次 Find，就更新整棵 Tree 的長相
- 把該點的 Parent 直接拉到 Root
### Running Time
對於一棵經過 Union by Rank 跟 Path Compression 的 Set
在執行上面的三個功能的「已緩衝的時間 amortized running time」是 $O(\alpha(n))$
其中 $\alpha(n)$ 是特殊的函數，就算 n 很大，這個函數的成長還是很小
而就實際面上來說通常 $\alpha(n) < 5$ 因此可以視為 Constant Time
---
# Kruskal Implement
- 一開始將每個點都 MakeUnionFind 一次，也就是將每個點都弄成一棵小樹
- 想要檢查一個 E 的兩點是否都在 T 裡面，那就只要檢查這兩個點有沒有同個 Representative 就好
- 如果兩個的 Representative 不同，就代表說是兩個不同的 Set，把這兩個所屬的 Set 使用 Union 合併起來
## 時間複雜度
```c
Kruskal(G,c)
1. {e1,e2,e3...em} sort edged in ascendimg order of their costs
2. T = {}
3. for each ei=(u,v)do
4. if( u and v are not connected by edges in T) then //different sub tree
5. T = T + {ei}//merge these two corresponding subtree
```
1. sorting 使用 heap sort 的話就是 nlogn，但是那個 n 是指 Edge 數量，所以這裡就是 mlogm
- 由於一個 Graph 的 Edge 數量最多就是 n^2^，其中 n 是點的數量
- 所以 mlogm 就是 2mlogn = mlogn
3. 迴圈就只要每次執行兩次 Find，有過判斷的話就一次的 Union；這兩個都是常數時間
如果想要更快的話，就是對 Sort 進行優化
由於我們是使用基本款，Comparison Based 的 Sort，但若使用其他的 Sort 達到線性時間，那這樣整個時間複雜度就會在下面迴圈的部分，也就是
$$
O(m\alpha(m,n))
$$
其中 m 是迴圈的次數，也就是 Edge 數量
$\alpha(m,n)$ 代表的是 Find (2m次) 跟 Union (n-1次)
由於 $\alpha(m,n)$ 可以視為常數時間，所以整體下來複雜度就是 O(m)
Sign in with Wallet
Connect another wallet