# Data Structure - Graph : 最小生成樹
###### tags: `Data Structure - Graph`
## 一 . 基本概念
### (一) . 定義名詞
1. $Spanning\ Tree$ : $T$若是$G(V,E)$的$spanning\ tree$
- $T$是一顆樹。
- $T$中的點『等於』$G$中的。
- $T$中的邊『存在於』$G$中的。
2. $Mining\ Spanning\ Tree$ : 對一個有權重的樹，$T$若是$G(V,E)$的$MST$。
- $T$是$G(V,E)$的$spanning\ tree$。
- $T$中的點權重和是$G$所有spanning tree中最小的。
3. $Mining\ Spanning\ Tree$的性質 ：
- $T$中的邊都存在$G$邊的集合中。(spanning tree性質)
- $T$中的點集合等$G$中的點集合。(spanning tree性質)
- $G$中的點為$n$個，則$T$中的邊必為$n-1$個。

## 二 . Kruskal algorithm
### (一) . Algorithm概念
1. 前提準備 ： 設下列四個集合。
- $V(G_0)$ : 母圖的點集合。
- $E(G_0)$ : 母圖的邊集合，**須先經過依照權重sort**。
- $V(G_1)$ : MST的點集合。(一開始為空)
- $E(G_1)$ : MST的邊集合。(一開始為空)
2. 演算法 ：
- 終止條件 ： 當$V(G_0)=V(G_1)$時。
- 迴圈行為 ： 將$E(G_0)-E(G_1)$的一個邊加入$E(G_1)$，此邊滿足：
- 權重必最小
- 不使MST有循環。
- 迴圈行為 ： 再將加入邊的兩端節點加入$V(G_1)$。
3. 時間複雜度 ： 對一個$G(V,E)$的圖，複雜度為$O(e*loge)$。
- 因為需要經過邊的排序。

## 三 . Prim algorithm
### (一) . Algorithm概念
1. 前提準備 ： 設下列四個集合。
- $E(G_0)$ : 母圖的邊集合 (使用table)。
- $E(G_1)$ : MST的邊集合。(使用table)。
2. 演算法 ：
- 起始化 ： 選一個點為邊的起始點(可以任選，不必為最小邊的兩端)。
- 終止條件 ： 當$E(G_0)=\ ∅$時。
- 迴圈行為 ： 根據$E(G_1)$所相連的邊中選一個加入$E(G_1)$，此邊滿足：
- 權重必最小
- 不使MST有循環。
- 迴圈行為 ： 再將相連卻非最小的邊去除$E(G_0)$。
3. 時間複雜度 ： 對一個$G(V,E)$的圖，複雜度會因為圖的儲存方式的不一樣而變。
- $adjacent\ list$ : $O(E+V*logV)$
- $adjacent\ array$ : $O(|V|^2)$

## 三 . Sollin algorithm
### (一) . Algorithm概念
1. 前提準備 ： 設下列四個集合。
- $E(G_0)$ : 母圖的邊集合 (使用table)。
- $E(G_1)$ : MST的邊集合。(使用table)。
2. 演算法 ：
- 終止條件 ： 當$E(G_0)=\ ∅$時。
- 迴圈行為 ： 根據$E(G_1)$所相連的邊中選一個加入$E(G_1)$，此邊滿足：
- 權重必最小
- 不使MST有循環。
- 迴圈行為 ： 再將相連卻非最小的邊去除$E(G_0)$。
3. 時間複雜度 ： 對一個$G(V,E)$的圖，複雜度會因為圖的儲存方式的不一樣而變。
- $adjacent\ list$ : $O(E+V*logV)$
- $adjacent\ array$ : $O(|V|^2)$