轉(zhuǎn)載請(qǐng)注明來源

最小生成樹簡(jiǎn)單的來說就是從無向連通圖的鄰接表或者鄰接矩陣中扣下來一棵權(quán)值最小的樹，他只有n-1條邊來連接n個(gè)頂點(diǎn)，并且不允許產(chǎn)生回路。

Kruskal算法首先要對(duì)邊進(jìn)行排序，sort一遍升序即可。然后要進(jìn)行的就是摳樹啦。最開始的時(shí)候把n個(gè)點(diǎn)看成獨(dú)立的n棵樹，然后按權(quán)值從小到大選擇邊，所選的邊連接的兩個(gè)頂點(diǎn)u，v應(yīng)屬于兩顆不同的樹，則成為最小生成樹的一條邊，并將這兩顆樹合并作為一顆樹。?重復(fù)直到所有頂點(diǎn)都在一顆樹內(nèi)或者有n-1條邊為止。

求最小生成樹要用到之前學(xué)過的并查集

參考：https://blog.csdn.net/luoshixian099/article/details/51908175

下面貼上代碼

#include <bits/stdc++.h> #define fi first #define se second #define pb push_back #define fio ios::sync_with_stdio(false);cin.tie(0); #define pii pair<int,int> #define vi vector<int> #define vc vector<char> #define pi 3.1415926 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1const int INF=0x3f3f3f3f; const int N=2e5+5;typedef long long ll; typedef double db; typedef unsigned long long ull; using namespace std;int n,m; int pre[N];struct edge {int start;int to;int value; }edges[N];void InitPre()//初始化pre數(shù)組 {for (int i=1;i<=n;i++){pre[i]=i;} }int findRoot(int n)//查找根節(jié)點(diǎn) {int r=n;while(pre[r]!=r)//查找這個(gè)點(diǎn)的根節(jié)點(diǎn) {r=pre[r];}//r現(xiàn)在是根節(jié)點(diǎn)int i=n,j;while(i!=r)//路徑壓縮，讓小弟直接歸老大直轄 {j=pre[i];pre[i]=r;i=j;}return r; }void join(int x,int y)//把各個(gè)連同分支連起來 {int r1=findRoot(x);int r2=findRoot(y);if(r1!=r2)//如果已經(jīng)連通不用管 {pre[r1]=r2;//不連通的時(shí)候隨便指定一個(gè)是另一個(gè)的老大 } }bool cmp(edge a,edge b) {return a.value<=b.value; }void kruskal() {int sumValue=0;//生成樹的權(quán)值int cnt=0;//已用邊的數(shù)量int start,to,value;for (int i=1;i<=m;i++){start=edges[i].start;to=edges[i].to;if(findRoot(start)!=findRoot(to)){cout<<start<<"---"<<to<<" "<<edges[i].value<<endl;sumValue+=edges[i].value;cnt++;join(start,to);}if(cnt>=n-1) break;}cout<<"SumValue: "<<sumValue<<endl; }int main() {//n個(gè)點(diǎn)m條邊cin>>n>>m;InitPre();for (int i=1;i<=m;i++){cin>>edges[i].start>>edges[i].to>>edges[i].value;}sort(edges+1,edges+1+m,cmp);cout<<endl<<endl;kruskal(); }

測(cè)試數(shù)據(jù)

7 9 1 2 28 1 6 10 2 3 16 2 7 14 3 4 12 4 5 22 4 7 18 5 6 25 5 7 24

?--------------------------------------------------------------------

更新一波，這個(gè)板子在一些數(shù)據(jù)下面會(huì)T掉，可能某些方面寫的不好。。

重新貼一個(gè)

1 #include <bits/stdc++.h> 2 #define fi first 3 #define se second 4 #define pb push_back 5 #define fio ios::sync_with_stdio(false);cin.tie(0); 6 #define pii pair<int,int> 7 #define vi vector<int> 8 #define vc vector<char> 9 #define pi 3.1415926 10 #define ls l,m,rt<<1 11 #define rs m+1,r,rt<<1|1 12 13 const int INF=0x3f3f3f3f; 14 const int N=2e5+5; 15 16 typedef long long ll; 17 typedef double db; 18 typedef unsigned long long ull; 19 using namespace std; 20 struct Edge 21 { 22 int u,v,w; 23 }edge[200005]; 24 25 int fa[5005],n,m,ans,eu,ev,cnt; 26 inline bool cmp(Edge a,Edge b) 27 { 28 return a.w<b.w; 29 }//快排的依據(jù) 30 inline int findRoot(int x){ 31 while(x!=fa[x]) x=fa[x]=fa[fa[x]]; 32 return x; 33 } 34 inline void kruskal(){ 35 sort(edge,edge+m,cmp);//將邊的權(quán)值排序 36 for(int i=0;i<m;i++){ 37 eu=find(edge[i].u), ev=find(edge[i].v); 38 if(eu==ev) continue;//若出現(xiàn)環(huán)，則continue 39 ans+=edge[i].w;//更新答案 40 fa[ev]=eu; cnt++; 41 if(cnt==n-1) break;//循環(huán)結(jié)束條件 42 } 43 } 44 int main(){ 45 scanf("%d%d",&n,&m); 46 for(int i=1;i<=n;i++) fa[i]=i;//初始化并查集 47 for(int i=0;i<m;i++) 48 scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w); 49 kruskal(); 50 printf("%d",ans); 51 return 0; 52 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/TheSilverMoon/p/9309772.html

總結(jié)

以上是生活随笔為你收集整理的最小生成树学习-Kruskal算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。