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 算法实现的一个函数，用于求解无向图的最小生成树。下面逐句进行代码分析：

1. `void MinTree_Kruskal(MGraph G)`：定义了一个函数 `MinTree_Kruskal`，参数为一个无向图 `G`。

2. `KEdge h[MAXNUM];`：定义了一个结构体数组 `h`，用于存储边的信息。

3. `int fat[MAX];`：定义了一个数组 `fat`，用于存储并查集中每个节点的前驱节点。

4. `int x,y;`：定义了两个变量 `x` 和 `y`，用于存储边的两个端点在并查集中的根节点。

5. `int i,j,k=1;`：定义了三个变量 `i`、`j` 和 `k`，其中 `k` 初始化为 `1`。

6. `int has=0;`：定义了一个变量 `has`，用于记录已经连接了多少条边。

7. `int minprice=0;`：定义了一个变量 `minprice`，用于存储最小生成树的代价。

8. `for(i=1; i<=G.vexnum; i++)`：循环遍历所有节点，即初始化并查集。

9. `for(j=i; j<=G.vexnum; j++)`：循环遍历节点 i 之后的所有节点。

10. `if(G.arcs[i][j].adj!=INFINITY)`：如果节点 i 和节点 j 之间有边相连，则执行以下代码。

11. `h[k].a=i; h[k].b=j; h[k].w=G.arcs[i][j].adj; k++;`：将边的信息存储到数组 `h` 中，包括边的两个端点和边的权值。

12. `for(i=1; i<=G.vexnum; i++)`：循环遍历所有节点，即初始化并查集。

13. `fat[i]=i;`：将每个节点的前驱节点初始化为自己。

14. `Sort(h,G.arcnum);`：对边的权值进行排序。

15. `for(i=1; i<=G.arcnum; i++)`：循环遍历所有边。

16. `if(has==G.vexnum-1) break;`：如果已经连接的边的数量等于节点数减一，则退出循环。

17. `x=Root(h[i].a,fat);`：找到节点 `a` 在并查集中的根节点。

18. `y=Root(h[i].b,fat);`：找到节点 `b` 在并查集中的根节点。

19. `if(x!=y)`：如果节点 `a` 和节点 `b` 不在同一个集合中，则执行以下代码。

20. `Unionn(x,y,fat);`：将节点 `a` 和节点 `b` 合并到同一个集合中。

21. `printf("%3c--%c%8d\n",G.vexs[h[i].a],G.vexs[h[i].b],h[i].w);`：输出连接的边的信息。

22. `minprice+=h[i].w;`：将连接的边的权值加到最小生成树的代价中。

23. `has++;`：已连接的边的数量加一。

24. `printf("\n\n使用kruskal算法得到的最小生成树的代价为: %d \n",minprice);`：输出最小生成树的代价。