一钉稍、prim算法
參考鏈接：
https://blog.csdn.net/gettogetto/article/details/53216951
思想：
Prim算法從任意一個(gè)頂點(diǎn)開始，每次選擇一個(gè)與當(dāng)前頂點(diǎn)集（MST點(diǎn)集）最近的一個(gè)頂點(diǎn)棺耍，并將兩頂點(diǎn)之間的邊加入到樹中贡未。稍微困難一點(diǎn)的地方在于當(dāng)前點(diǎn)集到 每個(gè)點(diǎn)的距離dist[i]數(shù)組，需要不斷地去更新維護(hù)蒙袍。
代碼：
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX (1<<31)-1
using namespace std;
int mp[1005][1005];
int dist[1005]; //記錄MST中的點(diǎn)集 到所有點(diǎn)的最短距離俊卤。
int vis[1005]; //標(biāo)記當(dāng)前點(diǎn)是否在MST中
int main() {
int n,m;
int l,r,w;
while(~scanf("%d%d",&n,&m)){
//輸入邊
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
mp[i][j] = MAX;
for(int i=0;i<m;i++){
scanf("%d%d%d",&l,&r,&w);
mp[r][l] = mp[l][r] = w;
}
//初始化MST, 第一個(gè)點(diǎn)加入MST;更新最短距離
memset(vis,0, sizeof(vis));
vis[1] = 1;
for(int i=1;i<=n;i++)
dist[i] = mp[1][i];
//遍歷n-1次找最近點(diǎn)的程序
int T=n-1;
int ok=1;
int sumVal = 0;
while(T--) {
int index = 0;
int minor = MAX;
//找距離MST點(diǎn)集最近的點(diǎn)
for (int i = 1; i <= n; i++)
if (!vis[i] && dist[i] < minor) {
minor = dist[i];
index = i;
}
//index加入MST中
if (!index) {
ok = 0;
break;
}
else {
vis[index] = 1;
sumVal += minor;
}
//更新 到每個(gè)點(diǎn)的最短距離
for (int i = 1; i <= n; i++)
if (!vis[i] && mp[index][i] < dist[i])
dist[i] = mp[index][i];
}
if(ok)
printf("%d\n",sumVal);
else
puts("-1");
}
return 0;
}
二、kruscal算法
思想：
不斷合并兩個(gè)不同的連通子圖害幅，最后成為一個(gè)連通圖消恍。具體地是 給所有邊按照升序排列，然后從頭遍歷每一條邊以现，如果這個(gè)邊的兩個(gè)頂點(diǎn)屬于不同連通圖狠怨，合并兩個(gè)連通圖约啊；如果是同一個(gè)連通圖，不操作（這里合并會(huì)形成環(huán)）佣赖。
難點(diǎn)在于“查詢兩個(gè)頂點(diǎn)是否屬于不同連通圖”和“合并兩個(gè)連通圖”可以用 并查集來實(shí)現(xiàn)恰矩。
代碼：
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Edge{
int l,r,w;
}E[50005];
int fa[10005];
bool cmp(Edge a, Edge b){
return a.w<b.w;
}
int find(int x){
if(x==fa[x])
return x;
return fa[x] = find(fa[x]);
}
int main() {
int n,m;
int a,b,w;
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;i++)
fa[i] = i;
for(int i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&w);
E[i].l = a;
E[i].r = b;
E[i].w = w;
}
//根據(jù)邊權(quán)值排序，升序
sort(E,E+m,cmp);
int cnt = 0; //加入生成樹中的邊個(gè)數(shù)
int sumVal = 0; //邊的權(quán)值和
for(int i=0;i<m;i++){
int x= find(E[i].l);
int y = find(E[i].r);
if(x!=y){
fa[x] = y;
cnt++;
sumVal+= E[i].w;
}
}
if(cnt==n-1)
printf("%d\n",sumVal);
else
puts("-1");
}
return 0;
}
三茵汰、二者比較
n為頂點(diǎn)個(gè)數(shù)枢里，m為邊的個(gè)數(shù)。
- prim算法需要構(gòu)造一個(gè)n*n的鄰接矩陣蹂午，故n不能太大栏豺。因此prim算法適合n較小(n<=1000)，邊較多的稠密圖豆胸。
- kruscal算法不用管點(diǎn)的數(shù)量奥洼，只要邊的數(shù)量<=10^6級(jí)別就行，所以kruscal的適用范圍更廣晚胡，而且代碼實(shí)現(xiàn)更為簡單灵奖，推薦~
