# 最小生成樹-Prim演算法介紹、證明、實作與複雜度分析
> 給定一連通帶權無向圖G(V,E)，有n條邊，一個生成樹T就是一個有n-1條邊的連通子圖，求出邊權和最小的T。
## Prim演算法概述
Prim演算法步驟如下：

1. 選擇圖上任一頂點為起始點
2. 初始化：$V_{new}=\{x\}$，$x$為選定的起始點，$E_{new}=\{\}$
3. 重複以下步驟直到$V_{new}=V$：
1. 在E中選權重最小的邊$(u,v)$滿足$u \in V_{new} ,v \in V\backslash V_{new}$
2. 將$v$加入$V_{new}$，$(u,v)$加入$E_{new}$
4. $(V_{new},E_{new})$即為T

同樣地，我們必須證明演算法的正確性。
## 正確性證明
設Prim產生的生成樹為$T$，最小生成樹為$T^*$，根據定義，T的邊權和$\geq$$T^*$的邊權和。
設$T$的邊由小到大為：$e_{k_1},e_{k_2},...,e_{k_n}$，$T^*$的邊由小到大為：$e_{g_1},e_{g_2},...,e_{g_n}$，其中$n=\mid V \mid -1$
設第一個屬於$T$卻不屬於$T^*$的邊為$e_{d_1}$，兩端點為$(v_s,v_{e_1})$，同時也存在第一個屬於$T^*$卻不屬於$T$的邊$e_{d_2}$，兩端點為$(v_s,v_{e_2})$。
兩個邊起點相同，由Prim演算法性質可知，$w(e_{d_2})\geq w(e_{d_1})$此時將$e_{d_2}$換成$e_{d_1}$，可得新生成樹$T_{new}$，且$T^*$的邊權和$\geq$$T_{new}$的邊權和，又因為$T^*$是最小生成樹，$T^*$的邊權和$＝$$T_{new}$的邊權和，以此類推，可得$T^*$的邊權和$＝$$T$的邊權和，故得證$T$是最小生成樹。

## Prim演算法實作
Prim演算法的實作基本上即是模擬上面步驟，故不贅述。
程式碼如下：

#include<bits/stdc++.h>
using namespace std;
#define Inf  2147483647

void Prim(vector<vector<int> > V){
	vector<int> d;  //記錄從U到V\U中各點的最短邊
	vector<int> U;  //記錄被加入到U中的點
	vector<bool> visited;  //記錄點是否被加入U中
	vector<int> M;  //記錄最終得到的各條邊
	d.resize(V.size());
	visited.resize(V.size());
	fill(visited.begin(), visited.end(), false);

	U.push_back(0);
	visited[0] = true;
	fill(d.begin(), d.end(), Inf);
	d[0] = 0;
	while (U.size() < V.size()){
		int x = U[U.size() - 1];         
		for (int i = 0; i < d.size(); i++)  {//更新從U到V-U中各點的最短邊
			if (!visited[i] && V[x][i] < d[i]){
				d[i] = V[x][i];
			}
		}
		int min = Inf;
		int index = 0;
		for (int i = 0; i < d.size(); i++) {  //尋找從U到V-U的最短邊
			if (d[i] < min && !visited[i]){
				min = d[i];
				index = i;
			}
		}
		if (index == 0){//不連通
			return;
		}
		visited[index] = true;
		U.push_back(index);
		M.push_back(min);
	}
	for (int i = 0; i < M.size(); i++){  //輸出所得最小生成樹的各條邊
		cout << M[i] << "  ";
	}
}

int main(){
	int n = 0;//節點數
	int m = 0;//邊數
	
	cin >> n>>m;
	vector<vector<int> > V;//圖(鄰接矩陣)
	V.resize(n);
	for (int i = 0; i < n; i++){
		V[i].resize(n);
		for (int j = 0; j < n; ++j){
			V[i][j] = Inf;
		}
	}
	for (int i = 0; i < m; i++){
            int u, v, w;
            cin >> u >> v >> w;
            V[u][v] = w;
            V[v][u] = w;
	}
	Prim(V);

	return 0;
}

## 複雜度分析
對於每個點都要用$O(\mid V \mid)$時間來尋找與之相連的最短邊，一共要加入$\mid V \mid$個點進集合，故複雜度為$O(\mid V \mid^2)$，與Kruskal相比，在邊的密度大時Prim有更好的表現。

## 參考資料

https://zh.wikipedia.org/wiki/%E6%99%AE%E6%9E%97%E5%A7%86%E7%AE%97%E6%B3%95
https://iter01.com/536986.html
IOICAMP2021講義