# 圖的最小生成樹
最小生成樹（Minimum Spanning Tree）是在給定無向圖 G(V,E) 中求一棵樹 T，使得 T 包含所有 V，且 T 的所有邊都來自 E，并且滿足整棵樹的邊權之和最小。
## prim 算法
稠密圖效果更佳。
### 偽碼
```c++
Prim(G,d[]){
init;
for(n){
u=使 d[u]最小的還未被訪問的頂點標號;
記 u 已被訪問;
for(從 u 出發所能到達的頂點 v){
if(v 未被訪問 &&
以 u 為中介點使得 v 與集合 S 的最短距離 d[v] 更優)
將 G[u][v] 賦值給 v 與集合 S 的最短距離 d[v];
}
}
}
```
### 鄰接矩陣
```c++
const int maxv=1000;
const int inf=0x3fffffff;
bool vis[maxv]={false};
int d[maxv];
int prim(){
fill(d,+maxv,inf);
d[0]=0;
int ans=0;
for(int i=0;i<n;i++){
int u=-1,min=inf;
for(int j=0;j<n;j++){
if(vis[j]==false && d[j]<min){
u=j;
min=d[j];
}
}
if(u==-1) return -1;
vis[u]=true;
ans+=d[u];
for(int v=0;v<n;v++){
if(vis[v]==false && G[u][v]!=inf &&
G[u][v]<d[v])
d[v]=G[u][v];
}
}
return ans;
}
```
### 鄰接表
```c++
const int maxv=1000;
vector<Node> Adj[maxv];
bool vis[maxv]={false};
int d[maxv];
int Prim(){
fill(d,d+maxv,inf);
d[0]=0;
int ans=0;
for(int i=0;i<n;i++){
int u=-1,min=inf;
for(int j=0;j<n;j++){
if(vis[u]==false && d[j]<min){
u=j;
min=d[j];
}
}
if(u==-1) return -1;
vis[u]=true;
ans+=d[u];
for(int j=0;j<Adj[u].size();j++){
int v=Adj[u][j].v;
int dis=Adj[u][j].dis;
if(vis[v]==false && dis<d[v])
d[v]=dis;
}
}
return ans;
}
```
## kruskal 算法
稀疏圖效果更佳。
### 偽碼
```c++
int kruskal(){
令最小生成樹的邊權之和為 ans、最小生成樹的當前邊數為 num;
將所有邊按邊權從小到大排序;
for(從小到大枚舉所有邊){
if(當前測試邊的兩個端點在不同的連通塊中){
將該測試邊加入最小生成樹中;
ans+=測試邊的邊權;
num++;
if(num==頂點數-1) break;
}
}
return ans;
}
```
### C++ 實現
```c++
const int maxv=1000;
struct edge{
int u,v; // 邊的兩端點
int cost; // 邊權
}E[maxv];
bool cmp(edge a, edge b){
return a.cost<b.cost;
}
int father[N]; // 并查集
int findFather(int x){
}
int kruskal(int n, int m){ // n=邊數，m=頂點數
int ans=0, num=0;
for(int i==1;i<=n;i++){
father[i]=i; // 并查集初始化
}
sort(E,E,cmp);
for(int i=0;i<m;i++){
int fau=findFather(E[i].u);
int fav=findFather(E[i].v);
if(fau!=fav){
father[fau]=fav;
ans+=E[i].cost;
num++;
if(num==n-1) break;
}
}
if(num!=n-1) return -1;
else return ans;
}
```
