克魯斯卡爾算法時間復雜度與排序算法sort有關，適合于稀疏圖。

#include <iostream> using namespace std; #define Maxsize 100 typedef char VertexType; typedef int EdgeType; typedef struct{VertexType Vex[Maxsize];EdgeType edge[Maxsize][Maxsize];int vexnum,arcnum; }MGraph; typedef struct{int a,b; //a、b為一條邊的兩個頂點int w; //w為邊的權值 }Road; Road road[Maxsize]; int v[Maxsize]; //定義并查集數組 int getRoot(int a){ //在并查集中查找根結點 while(a!=v[a])a=v[a];return a; }void Kruskal(MGraph G,int &sum,Road road[]){int i,N,E,a,b;N=G.vexnum;E=G.arcnum;sum=0;for(i=0;i<N;i++)v[i]=i;sort(road,E); //對road數組中的E條邊按其權值從小到大排序for(i=0;i<E;i++){a=getRoot(road[i].a);b=getRoot(road[i].b);if(a!=b){ //不在一個集合中 v[a]=b; //合并兩棵樹sum+=road[i].w; //求生成樹權值 }} }

?

總結

以上是生活随笔為你收集整理的求最小生成树-Kruskal（克鲁斯卡尔算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

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