求最小生成树 —— 卡鲁思卡尔算法
算法思想：
将图中边按照权值从小到大排序（可以使用堆排序），然后从最小的边开始扫描，设置一个边的集合来记录，如果该边并入不构成回路（可以使用并查集来判断是否构成回路）的话，则将该边并入当前生成树。直到所有的边都检测为止。
实现代码：
#define MAXSIZE 100typedef struct {int a, b; //边的两个顶点int weight; //边的权值
} Edge; //边结构体int Find(int *parent, int x) {while(parent[x]>=0) //循环向上寻找下标为x顶点的根x=parent;return x; //while循环结束时找到了根的下标
}Edge edges[MaxEdge]; //边数组
int parent[MaxVex]; //父亲顶点数组（查并集）void MiniSpanTree_Kruskal(Mgraph G) {int i, n, m;sort(edges); //按权值由小到大对边排序for(i=0; i%d”, edges[i].a, edges[i].b);}}
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！