注：本文算法使用鏈式前向星數據結構實現。學習鏈接：鏈式前向星-學習筆記
一、Prim算法
普通prim算法模板：
//用前向星錄數據的時候記得把head初始化為-1 fill(dist,dist+LEN,MAX); memset(vis,0,sizeof vis); int ans=0; dist[1]=0; //如果題目要求輸出最小生成樹，就把題目要求的源點s的dist設為0 while(1){ //如果題目要求判斷最小生成樹是否能覆蓋所有邊，這個循環條件應該是i=n;while(n--)循環n次。 int u=-1,d=MAX;for(i=1;i<=N;i++){if(!vis[i] && dist[i]<d){u=i;d=dist[i];}}if(u<0) break; //如果題目要求判斷最小生成樹是否能覆蓋所有邊，出現這樣的情況說明不能覆蓋所有邊。 vis[u]=1;ans+=dist[u];for(i=head[u];~i;i=mp[i].next){ //用前向星遍歷u點所有的后繼。i是各個后繼點在mp的下標，mp[to]是u的各個后繼點 int to=mp[i].to;if(!vis[to] && mp[i].w<dist[to]){//如果這個點沒有被訪問過、并且u->v的路徑比點集S到v的路徑要短，則更新。 dist[to]=mp[i].w;}} } O("%d\n",ans);
堆優化的prim算法：
堆結構：
struct cmp{bool operator () (int a,int b){return dist[a]>dist[b];} }; priority_queue<int,vector<int>,cmp> pq;
算法代碼：
int ans=0; dist[1]=0; pq.push(1); while(!pq.empty()){int u=pq.top();pq.pop();if(vis[u]) continue;vis[u]=1;ans+=dist[u];for(i=head[u];~i;i=mp[i].next){int to=mp[i].to;if(!vis[to] && mp[i].w<dist[to]){dist[to]=mp[i].w;pq.push(to);}} } O("%d\n",ans);
?
二、Kruskal算法
1.建立邊表數據結構
typedef struct edge{int u,v,w;edge(int u=0,int v=0,int w=0):u(u),v(v),w(w){}bool operator < (const edge& obj) const{return w<obj.w;} }edge; edge mp[LEN*LEN];
2.編寫并查集模板（以下代碼沒有寫合并的Union操作。這個操作在主代碼執行的時候已經實現）
int fa[LEN]; int init(){int i;FF(i,LEN) fa[i]=i; } int findFa(int x){if(x==fa[x]) return x;int r=x;while(r!=fa[r]){r=fa[r];}int t=x;while(x!=fa[x]){t=fa[x];fa[x]=r;x=t;}return r; }
3.編寫主代碼
sort(mp,mp+cnt); FF(i,cnt){int fa_u=findFa(mp[i].u);int fa_v=findFa(mp[i].v);if(fa_u!=fa_v){ans+=mp[i].w;fa[fa_u]=fa_v;edge_cnt++;if(edge_cnt>=N-1) break;} } O("%d\n",ans);
注意：
①邊表的范圍要開大，因為邊的數目可能是頂點數目的平方（準確說，有向圖邊樹E=N*(N-1) ）
②Prim算法在錄邊的數據的時候，因為是無向圖，一條邊要錄成兩條。Kruskal就沒有這種必要了。
③各種初始化代碼（比如并查集的init() ）要注意加上。
?
打個OJ測試一下吧！
OJ鏈接：還是暢通工程
AC代碼：
#include <stdio.h> #include <memory.h> #include <math.h> #include <string> #include <vector> #include <set> #include <stack> #include <queue> #include <algorithm> #include <map>#define I scanf #define OL puts #define O printf #define F(a,b,c) for(a=b;a<c;a++) #define FF(a,b) for(a=0;a<b;a++) #define FG(a,b) for(a=b-1;a>=0;a--) #define LEN 1010 #define MAX (1<<30)-1 #define V vector<int>using namespace std;int N; int fa[LEN]; int init(){int i;FF(i,LEN) fa[i]=i; } int findFa(int x){if(x==fa[x]) return x;int r=x;while(r!=fa[r]){r=fa[r];}int t=x;while(x!=fa[x]){t=fa[x];fa[x]=r;x=t;}return r; }typedef struct edge{int u,v,w;edge(int u=0,int v=0,int w=0):u(u),v(v),w(w){}bool operator < (const edge& obj) const{return w<obj.w;} }edge; edge mp[LEN*LEN]; int cnt=0;int main(){ // freopen("還是暢通工程.txt","r",stdin);int i,j,u,v,w;while(scanf("%d",&N),N){init();cnt=0;int ans=0;int edge_cnt=0;i=(N*(N-1))/2;while(i--){I("%d%d%d",&u,&v,&w);mp[cnt++]=edge(u,v,w); // mp[cnt++]=edge(v,u,w); }sort(mp,mp+cnt);FF(i,cnt){int fa_u=findFa(mp[i].u);int fa_v=findFa(mp[i].v);if(fa_u!=fa_v){ans+=mp[i].w;fa[fa_u]=fa_v;edge_cnt++;if(edge_cnt>=N-1) break;}}O("%d\n",ans);}return 0; }
?
)
