按照權值排序可得，就有如下順序:

1. 1-2 1

2. 1-4 2

3. 1-5 2

4. 2-5 3

5. 2-3 4

6. 4-5 4

每次選取最小邊泉，判斷是否同屬一個集合，如果不屬于同一集合，就把它加到左端點集合中，也就是說，兩個點不屬于一個集合說明這條邊不在樹中，即可將其加入左端點集合。

下面我們模擬算法過程:

?

每次，直接把每次找到的邊找到，就可以了！

對于Kruscal它更適合于稀疏圖，借助貪心與并查集實現，我們看懂了上述算法實現過程，很容易寫出算法！

代碼實現

#include<iostream> #include<queue> #include<algorithm> #include<set> #include<cmath> #include<vector> #include<map> #include<stack> #include<bitset> #include<cstdio> #include<cstring> //---------------------------------Sexy operation--------------------------//#define cini(n) scanf("%d",&n) #define cinl(n) scanf("%lld",&n) #define cinc(n) scanf("%c",&n) #define cins(s) scanf("%s",s) #define coui(n) printf("%d",n) #define couc(n) printf("%c",n) #define coul(n) printf("%lld",n) #define debug(n) printf("%d_________________________________\n",n); #define speed ios_base::sync_with_stdio(0) #define file freopen("input.txt","r",stdin);freopen("output.txt","w",stdout) //-------------------------------Actual option------------------------------// #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define Swap(a,b) a^=b^=a^=b #define Max(a,b) (a>b?a:b) #define Min(a,b) a<b?a:b #define mem(n,x) memset(n,x,sizeof(n)) #define mp(a,b) make_pair(a,b) #define pb(n) push_back(n) #define dis(a,b,c,d) ((double)sqrt((a-c)*(a-c)+(b-d)*(b-d))) //--------------------------------constant----------------------------------//#define INF 0x3f3f3f3f #define esp 1e-9 #define PI acos(-1) using namespace std; typedef pair<int,int>PII; typedef pair<string,int>PSI; typedef long long ll; //___________________________Dividing Line__________________________________/int n,m; int father[1100000]; struct node {int x;int y;int k; }Q[1100000]; int find(int x) {if(father[x]==x)return x;return father[x]=find(father[x]); } bool cmp(node a,node b) {return a.k<b.k; } int main() {while(~scanf("%d %d",&n,&m)){int cont=0,sum=0,st=0;for(int i=0;i<m;i++){scanf("%d %d %d",&Q[i].x,&Q[i].y,&Q[i].k);cont+=Q[i].k;}sort(Q,Q+m,cmp);for(int i=1;i<=n;i++) father[i]=i;for(int i=0;i<m;i++){int tx=find(Q[i].x);int ty=find(Q[i].y);if(tx!=ty){sum+=Q[i].k;st++;father[tx]=ty;if(st==n-1)break;}}printf("%d\n",sum);}return 0; }

?

總結

以上是生活随笔為你收集整理的疯子的算法总结10--最小生成树Kruscal的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。