版本 1c6074a6f406681d5557d485bd687b46ae640e92
Changes from 1c6074a6f406681d5557d485bd687b46ae640e92 to current
#MST(Minimum Spanning Tree, 最小生成樹)
##Spanning Tree(生成樹)
1.一棵<b>包含圖上所有點</b>的樹，稱作該圖的生成樹
#MST (Minimum Spanning Tree, 最小生成樹)
##Spanning Tree (生成樹)
1. 一棵<b>包含圖上所有點</b>的樹，稱作該圖的<b>生成樹</b>
2.一張圖的生成樹可能會有很多種
2. 一張圖的生成樹可能會有很多種
3.完全連通圖才有生成樹(不連通時，則稱為生成森林)
3. <b>完全連通圖</b>才有生成樹 (不連通時，則稱為生成森林)
4.生成樹的權重為樹上每條邊的權重總和
4. 生成樹的權重為樹上每條邊的權重總和
##Minimum Spanning Tree
擁有最小權重的生成樹，稱為最小生成樹
###Kruskal’s algorithm(greedy based)
1.依照權重排序
擁有<b>最小權重</b>的生成樹，稱為最小生成樹
2.選擇較小的邊，並邊檢查是否有迴圈
###Kruskal’s Algorithm (greedy based)
1. 依照權重排序
2. 選擇較小的邊，並檢查是否有環
* Psuedocode
```c++
KRUSKAL(G):
A = ∅
foreach v ∈ G.V:
MAKE-SET(v)
foreach (u, v) in G.E ordered by weight(u, v), increasing:
if FIND-SET(u) ≠ FIND-SET(v):
A = A ∪ {(u, v)}
UNION(u, v)
return A
```
totalcost← 0
for each v ∈ V
do MAKE-SET (v)
sort the edges into non-decreasing order by weight
for each edge (u, v) ∈ E, taken in non-decreasing order
do if FIND-SET (u) ≠ FIND-SET (v)
then UNION (u, v)
totalcost← totalcost+ w(u, v)
return totalcost
* 時間複雜度O(ElgE)
###Prim’s algorithm(relaxation based)
```c++
const int V = 100, E = 1000; // V = vertice, E = edge
struct Edge{int a, b, c;} e[E]; // edge list
bool operator<(const Edge& e1, const Edge& e2){ return e1.c < e2.c;}
// disjoint-sets forest
int p[V];
int init(){ for(int i=0; i<V; ++i) p[i] = i;}
int find(int x){ return x == p[x] ? x : (p[x] = find(p[x]));}
void union(int x, int y){ p[find(x)] = find(y);}
void Kruskal(){
init();
sort(edge, edge+E); // 圖上所有邊，依照權重大小，由小到大排序。O(NlogN)
for(int j = 0; i < V-1 && j < E; j ++){ // 窮舉圖上所有邊，嘗試作為最小生成樹（森林）
if(find(e[j].a) == find(e[j].b)) // 產生環，則捨棄。
continue;
union(e[j].a, e[j].b); // 產生橋，則以此邊連接兩棵MSS。
}
}
```
* 時間複雜度 O(ElgE)
###Prim’s Algorithm (relaxation based)
1.所有節點設為<b>未拜訪</b>過 (設為INF)
2.令d[i]為到節點i的距離(每次皆考慮鄰近節點)
3.考慮所有鄰近<b>樹</b>且<b>未拜訪過</b>的節點i，選擇距離最近的節點，並檢查是否有環
4.更新拜訪過節點與鄰近節點d[i]
```c++
#include <cstdio>
using namespace std;
int main()
{
int w[9][9]; // adjacency matrix
int d[9]; // 紀錄目前的MST到圖上各點的距離
int parent[9]; // 紀錄各個點在MST上的父親是誰
bool visit[9]; // 紀錄各個點是不是已在MST之中
void prim(){
for(int i=0; i<9; i++) visit[i] = false;
for(int i=0; i<9; i++) d[i] = 1e9;
d[0] = 0; // 可以選定任何點作為樹根，這裡以第零點作為樹根。
parent[0] = 0;
for(int i=0; i<9; i++){
int a = -1, b = -1, min = 1e9;
for(int j=0; j<9; j++)
if(!visit[j] && d[j] < min){
a = j; // 記錄這一條邊
min = d[j];
}
if(a == -1) break; // 與起點相連通的MST都已找完
visit[a] = true;
// d[a] = 0; // 註解後，得到MST每條邊權重。
for(b=0; b<9; b++)
if(!visit[b] && w[a][b] < d[b]){
d[b] = w[a][b]; // 離樹最近，不是離根最近。
parent[b] = a;
}
}
}
```
* 時間複雜度 O(𝑉")
With Binary-Heap : O( (V+E)logV)
參考來源：
演算法筆記 http://www.csie.ntnu.edu.tw/~u91029/SpanningTree.html
維基百科 https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
