克鲁斯卡尔算法时间复杂度与排序算法sort有关，适合于稀疏图。
#include <iostream>using namespace std;#define Maxsize 100typedef 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;//求生成树权值 }} }
