最小生成樹是一個連通加權(quán)無向圖中一棵權(quán)值最小的生成樹。
Prim算法思想：
設(shè)圖G頂點(diǎn)集合為U怨酝，首先任意選擇圖G中的一點(diǎn)作為起始點(diǎn)a傀缩，將該點(diǎn)加入集合V，再從集合U-V中找到另一點(diǎn)b使得點(diǎn)b到V中任意一點(diǎn)的權(quán)值最小农猬，此時將b點(diǎn)也加入集合V赡艰；以此類推，現(xiàn)在的集合V={a斤葱，b}慷垮，再從集合U-V中找到另一點(diǎn)c使得點(diǎn)c到V中任意一點(diǎn)的權(quán)值最小，此時將c點(diǎn)加入集合V苦掘，直至所有頂點(diǎn)全部被加入V换帜，此時就構(gòu)建出了一棵MST（Minimum Spanning Tree，最小生成樹）鹤啡。因?yàn)橛蠳個頂點(diǎn)惯驼，所以該MST就有N-1條邊，每一次向集合V中加入一個點(diǎn)递瑰，就意味著找到一條MST的邊祟牲。
代碼實(shí)現(xiàn)：
//最小生成樹
int map[N][N]; //存i到j(luò)的路徑
int vis[N]; //存該節(jié)點(diǎn)是否已經(jīng)選取過了
int dist[N]; //樹到其它各個節(jié)點(diǎn)的距離
int prim()
{
int sum =0;
for(int i=0;i<n;i++)
dist[i]= map[0][i];
vis[0]=true;
for(int i=1;i<=n-1;i++) //找n-1條邊
{
int minn=INT_MAX;
int index=0;
for(int j=0;j<n;j++) //找當(dāng)前樹到其它節(jié)點(diǎn)的最短路徑加入樹
{
if(vis[j]==false&&dist[j]<minn)
{
minn=dist[j];
index=j;
}
}
sum+=minn;
vis[index]=true;
for(int j=0;j<n;j++) //更新樹到樹外其它節(jié)點(diǎn)的最小距離
{
if(vis[j]==false&&dist[j]>map[index][j])
dist[j]=map[index][j];
}
}
return sum;
}
時間復(fù)雜度：O(n^2)
Kruskal算法思想：
Kruskal算法是基于貪心的思想得到的。首先我們把所有的邊按照權(quán)值先從小到大排列抖部，接著按照順序選取每條邊说贝，如果這條邊的兩個端點(diǎn)不屬于同一集合，那么就將它們合并慎颗，直到所有的點(diǎn)都屬于同一個集合為止乡恕。至于怎么合并到一個集合，需要使用并查集俯萎。換而言之傲宜，Kruskal算法就是基于并查集的貪心算法。
基本思想是以邊為主導(dǎo)地位夫啊，始終都是選擇當(dāng)前可用的最小權(quán)值的邊函卒，步驟如下：
- 設(shè)一個有n個頂點(diǎn)的連通網(wǎng)絡(luò)為G（V,E），最初先構(gòu)造一個只有n個頂點(diǎn)撇眯，沒有邊的非連通圖T（V,?）报嵌，圖中每個頂點(diǎn)自成一個連通分量
- 將原圖中的所有邊按權(quán)值從小到大排序
- 從權(quán)值最小的邊開始虱咧，如果這條邊連接的兩個頂點(diǎn)于圖T中不在同一個連通分量中，則添加這條邊到圖T中
- 重復(fù)3锚国，直至T中所有頂點(diǎn)在同一個連通分量中為止
代碼實(shí)現(xiàn)：
#include <iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define maxn 110; //最多點(diǎn)個數(shù)
int fa[110]; //并查集存根節(jié)點(diǎn)
int n, m; //頂點(diǎn)個數(shù)腕巡， 邊數(shù)
struct Edge{
int x, y;
int val;
}edge[5000];
bool cmp(Edge a, Edge b)
{
return a.val < b.val;
}
int findfa(int x) //尋找所在樹的根節(jié)點(diǎn)，判斷是否在同一個連同分量的依據(jù)
{
if(fa[x] != x)
fa[x] = findfa(fa[x]);
return fa[x];
//return fa[x] == x ? x : (fa[x] = findfa(fa[x]));
}
int Union(int x, int y) //并查集合并兩棵樹
{
fa[findfa(x)] = findfa(y);
}
int Kruskal()
{
int cnt = 0;
long sum = 0;
for(int i=1; i<=n; i++) //頂點(diǎn)的編號為[1..n]
fa[i] = i;
sort(edge, edge+m, cmp); //把邊從小到大排序跷叉，m為邊的數(shù)目
for(int i=0; i<m; i++)
{
int fx = findfa(edge[i].x);
int fy = findfa(edge[i].y);
if(fx != fy)
{
Union(fx, fy);
cnt++;
sum += edge[i].val;
if(cnt >= n-1) break; //n-1條邊均加入同一個集合中
}
}
return sum;
}
int main()
{
cin>>n>>m;
for(int i=0; i<m; i++)
cin>>edge[i].x>>edge[i].y>>edge[i].val;
cout<<Kruskal()<<endl;
return 0;
}
/*
5 7
1 2 3
1 5 1
2 5 4
2 3 5
3 4 2
3 5 6
4 5 7
*/
時間復(fù)雜度： O(E*logE)
Kruskal算法每次要從都要從剩余的邊中選取一個最小的邊逸雹。通常我們要先對邊按權(quán)值從小到大排序，這一步的時間復(fù)雜度為為O(ElogE)云挟。Kruskal算法的實(shí)現(xiàn)通常使用并查集梆砸，來快速判斷兩個頂點(diǎn)是否屬于同一個集合。最壞的情況可能要枚舉完所有的邊园欣，此時要循環(huán)E次帖世，所以這一步的時間復(fù)雜度為O(Eα(V))，其中α為Ackermann函數(shù)沸枯，其增長非常慢日矫，我們可以視為常數(shù)。所以Kruskal算法的時間復(fù)雜度為O(ElogE)绑榴。
總結(jié)：
Prim和Kruskal的貪心策略是一樣的哪轿，都是選取耗費(fèi)最小的邊：
- 對于Prim, 其選取的邊（u,v）必有一個頂點(diǎn)已經(jīng)被覆蓋，另一個頂點(diǎn)未被覆蓋翔怎，適用于稠密圖窃诉。
- 對于Kruskal, 其選取的邊（u,v）任意，只要這個邊的加入不會使被覆蓋的頂點(diǎn)構(gòu)成回路赤套，適用于稀疏圖飘痛。
