---
# System prepended metadata

title: Greedy Algorithm / Spanning Tree
tags: [演算法(交大OCW)]

---

---
title: Greedy Algorithm / Spanning Tree
tags: 演算法(交大OCW)
---
# Spanning Tree

第四台在拉線的時候，一定是從現有的線路拉線到還沒拉線的地方...

## 輸入

一個無方向性 G(V,E)，每條 E 的權重均 ≧ 0
- 去找出一個 E 的集合，使得權重加起來最小
- 並且所有的點都有連到 (is connected)

>可以回去複習 Connected 的定義


![](https://drive.google.com/uc?id=19hahax6IuiWHQVBfqfntUtBD2xiLJQR2&export=download)


## 輸出

我要找到一個 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}這條，但是因為它會跟已經選好的形成環，所以就跳過他

![](https://drive.google.com/uc?id=1FdH0M97skylp93lfpV6h9_sagbriR2lM&export=download)

最後就會得到這棵樹

![](https://drive.google.com/uc?id=1NnEf3mUMDlsFiDGRpWQxy6c6BcnLqbUv&export=download)

:::warning
這就很像把很多棵小樹併成一棵大樹
:::

# Robert C. Prim 1957

思路跟 Kruskal 不一樣

```c
1. 由於最後一定要連接所有點，所以一開始就先隨便挑一個點
2. 每次從已經選好的所有點去看，看哪條 E 的花費最少，就選那條 E，以及與之相連的 node
```

下圖就是從 D 點出發，將 D 塞入已選好的點
往外看出去發現上面的路比較便宜，所以就走上面，並把 D 塞入已選好的點

![](https://drive.google.com/uc?id=1cl54ZQDVUrkRD7PuvKr2W17cZJG9KWsp&export=download)

此時選好的點有 2 個，所以就從 A 跟 D 看出去，哪條 E 比較便宜
發現是下面 {D,F} 那條，於是就把 F 塞入已選好的點

![](https://drive.google.com/uc?id=1IcU0bpfP_Ij52EG-6hoyachtgE2rkzTd&export=download)

最後一樣可以得到

![](https://drive.google.com/uc?id=1NnEf3mUMDlsFiDGRpWQxy6c6BcnLqbUv&export=download)

:::warning
跟 Kruskal 的差異在於，從頭到尾都維持一棵樹
:::

# Reverse Delete

:::info
整個逆向操作起來，用拔的，把不需要的拔掉

因為一棵 Tree 只有 n-1 個 E，所以拔到剩 n-1 個 E 就好
每次就挑最貴的 E 下手。不過拔的時候要注意不能讓 Tree 變成兩半
:::

![](https://drive.google.com/uc?id=19WoYoXVXkvR2rS9YKC_Y1oQ3qxIeUiiX&export=download)

---

# 總結

- 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 就會被孤立

![](https://drive.google.com/uc?id=1Zg8-_58JZ3ydb07qtPamTg_NGvvG7Yyr&export=download)

:::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^'^

圖示如下

![](https://drive.google.com/uc?id=1AcwFMnH4dyv3nbSEXUigR6YZeHTYjfKz&export=download)

此時如果把 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 合併起來

![](https://drive.google.com/uc?id=1SaRSz2AeSwinOpwSo_ZNPHlJSZHfA_LX&export=download)

## 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)