void MinTree_Kruskal(MGraph G) { //kruskal算法运用并查集知识 KEdge h[MAXNUM]; //存储边信息 int fat[MAX]; //fat[i]存储i的前驱结点 int x,y; int i,j,k=1; int has=0; //已经连接了多少条边 int minprice=0; for(i=1; i<=G.vexnum; i++) //初始化 { for(j=i; j<=G.vexnum; j++) { if(G.arcs[i][j].adj!=INFINITY) { h[k].a=i; h[k].b=j; h[k].w=G.arcs[i][j].adj; k++; } } } for(i=1; i<=G.vexnum; i++) //初始化 { fat[i]=i; } Sort(h,G.arcnum); //kruskal思想，排序权值 printf("使用kruskal算法得到的最小生成树的各边及其权值为:\n\n"); printf(" 结点 权值\n"); for(i=1; i<=G.arcnum; i++) { if(has==G.vexnum-1) break;//树的边数等于顶点-1 x=Root(h[i].a,fat); //寻找根结点 y=Root(h[i].b,fat); //寻找根结点 if(x!=y) //不在一个集合 { Unionn(x,y,fat); printf("%3c--%c%8d\n",G.vexs[h[i].a],G.vexs[h[i].b],h[i].w); minprice+=h[i].w; has++; } } printf("\n\n使用kruskal算法得到的最小生成树的代价为: %d \n",minprice); }代码分析

这段代码实现了最小生成树的 Kruskal 算法。具体实现过程如下：

- 定义 KEdge 类型，用于存储边信息，包括边的起点、终点和权值。
- 定义 fat 数组，表示每个节点的前驱结点，初始化为节点本身。
- 将所有边信息存储到 h 数组中，并按照权值从小到大排序。
- 依次遍历 h 数组中的每条边，如果当前已经连接的边数等于总节点数-1，则退出循环。
- 对于每条边，通过 Root 函数查找其起点和终点所在的集合的根节点，如果不在同一个集合中，则将它们合并，并输出该边的信息。
- 最后输出最小生成树的代价。

其中，Root 和 Unionn 函数是对并查集的操作，用于查找根节点和合并两个集合。