---
# System prepended metadata

title: 'Data Structure - Graph : 最小生成樹'
tags: [Data Structure - Graph]

---

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