Krsukal算法构造最小生成

1. 问题

Krsukal 算法通过不断加入图中最小的边，若构成回路则不添加，通过并查集来检查是否构成回路，通过最小堆对边进行存储，直到将图的边加到顶点-1为止，如果添加不到顶点-1条边则构不成最小生成树。

2、分析

3、设计

Int Krsukal(MGraph Graph,LGraph MST)
{
Int totalweight,ecount;
/定义边数组与顶点数组/
Eset,Vset;
初始化顶点数组都使每个顶点为根节点，Vset[x]=-1;
/定义并查集/
/初始化边数组，使加入的每一个边不重复/
/建立最小堆/
Heap;
/将边数组保存在最小堆中/
Int nextedge;
/定义下一个加进的边，初始值为边数组的最后一个元素Graph->ne/
while(ecountnv-1){
Nextedge=getedge(…????/定义函数将边数组中的0位置与nextedge位置交换，调整最小堆/
If(Nextedge<0)break;/如果边数组为空，跳出循环/
If(checkis())/检查是否构成回路/
Insert(MST,Eset[Nextedge])
Ecount++;
Totalweight+=Eset[nextedge].weight;
}
}

4、源码

源码地址：https://github.com/ACynj/ynjkruskal.git