#include<stdio.h> #include<stdlib.h> #include<string.h> #include<limits.h> #include"MGraph.h" #define MAXE 100 typedef struct { int u; //边的起始顶点 int v; //边的终止顶点 int w; //边的权值 } Edge; void SortEdge(Edge E[],int e); //对E数组按权值递增排序 void Kruskal(MGraph g); // 用克鲁斯卡尔算法构造网G的最小生成树T，输出T的各条边 int main() { MGraph g; CreateGraphF (g); // 利用数据文件创建无向图 Display(g); // 输出无向图 printf("用克鲁斯卡尔构造g的最小生成树的各条边:\n"); Kruskal(g); // 用克鲁斯卡尔算法构造最小生成树 return 0; } void SortEdge(Edge E[],int e) //对E数组按权值递增排序 { int i,j,k=0; Edge temp; for (i=1;i<e;i++) { temp=E[i]; j=i-1; //从右向左在有序区E[0..i-1]中找E[i]的插入位置 while (j>=0 && temp.w<E[j].w) { E[j+1]=E[j]; //将权值大于E[i].w的记录后移 j--; } E[j+1]=temp; //在j+1处插入E[i] } } void Kruskal(MGraph g) //输出求得的最小生树的所有边 { // 用克鲁斯卡尔算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边 /********** Begin **********/ /********** End **********/ } 补充这个代码

### 补充完整的克鲁斯卡尔算法实现 克鲁斯卡尔算法的核心在于按照边的权重对所有边进行排序，并逐步选择不构成环路的边加入最小生成树中。此过程依赖于并查集（Union-Find）来高效判断新增边是否会引入环路[^1]。 以下是针对用户需求补充的 `Kruskal` 函数具体代码逻辑，基于之前定义的数据结构和辅助函数展开实现。 --- #### 完整的 Kruska 算法实现 ```c #include <stdio.h> #include <stdlib.h> /// 边的定义 typedef struct { int u; // 边的一个端点 int v; // 边的另一个端点 int weight; // 边的权值 } Edge; /// 图的邻接矩阵定义 #define MAXV 100 // 假设最大顶点数为100 typedef struct { int edges[MAXV][MAXV]; // 邻接矩阵存储边的信息 int nvertices; // 图的实际顶点数目 int nedges; // 图的实际边数目 } MGraph; /// 并查集父节点数组 int parent[MAXV]; /// 初始化并查集 void init_set(int size) { for (int i = 0; i < size; ++i) { parent[i] = i; // 初始状态下每个结点自成一派 } } /// 查找根节点（路径压缩） int find_set(int x) { if (parent[x] != x) { parent[x] = find_set(parent[x]); // 路径压缩优化 } return parent[x]; } /// 合并两个集合 void union_set(int x, int y) { int fx = find_set(x); int fy = find_set(y); if (fx != fy) { parent[fy] = fx; // 将fy所在的集合挂载到fx下 } } /// 添加边至全局边列表 Edge edgeList[1000]; // 存储所有可能存在的边 int totalEdges = 0; void add_edge_to_list(int u, int v, int w) { edgeList[totalEdges].u = u; edgeList[totalEdges].v = v; edgeList[totalEdges].weight = w; totalEdges++; } /// 对边列表中的元素依据 weight 字段升序排列 void sort_edges() { for (int i = 0; i < totalEdges - 1; ++i) { for (int j = 0; j < totalEdges - i - 1; ++j) { if (edgeList[j].weight > edgeList[j + 1].weight) { Edge temp = edgeList[j]; edgeList[j] = edgeList[j + 1]; edgeList[j + 1] = temp; } } } } /// 使用克鲁斯卡尔算法求解最小生成树 void Kruskal(MGraph g) { int mst_weight = 0; // 记录最终得到的最小生成树总重量 /// 构建边表 for (int i = 0; i < g.nvertices; ++i) { for (int j = i + 1; j < g.nvertices; ++j) { if (g.edges[i][j] != 0 && g.edges[i][j] != INT_MAX) { add_edge_to_list(i, j, g.edges[i][j]); } } } /// 排序边表 sort_edges(); /// 初始化并查集 init_set(g.nvertices); /// 开始遍历每一条边 int count = 0; // 已经选入最小生成树的边数量 for (int k = 0; k < totalEdges && count < g.nvertices - 1; ++k) { int u = edgeList[k].u; int v = edgeList[k].v; if (find_set(u) != find_set(v)) { // 若两点不在同一个集合，则可以安全添加这条边 printf("Adding edge (%d-%d) with cost %d\n", u, v, edgeList[k].weight); mst_weight += edgeList[k].weight; union_set(u, v); count++; } else { continue; // 否则跳过当前边以免造成环路 } } /// 输出结果 if (count == g.nvertices - 1) { printf("Total minimum spanning tree cost is: %d\n", mst_weight); } else { printf("No MST found.\n"); } } ``` 上述代码实现了完整的克鲁斯卡尔算法逻辑，能够处理任意无向带权图的最小生成树问题[^2]。 --- ### 关键点解析 1. **边的提取与排序**： - 遍历邻接矩阵，将有效边存入全局变量 `edgeList` 中。 - 使用冒泡排序对边按权重从小到大排序，复杂度为 \(O(E^2)\)，可替换为更高效的排序算法如快速排序以降低时间开销[^3]。 2. **并查集的作用**： - 并查集用于动态维护连通分量关系，确保每次新加入的边不会形成回路。 - 路径压缩技术显著提升了查询效率，使得单次操作接近常数时间 \(O(\alpha(V))\)【\(\alpha\) 是反阿克曼函数】[^4]。 3. **终止条件**： - 当已选边的数量达到 \(|V|-1\) 或者所有边均被尝试完毕时停止循环。 - 如果无法选出足够的边，则说明原图非连通，返回提示信息 “No MST found.”。 --- ### 示例运行 假设有如下邻接矩阵表示的无向图： | | A | B | C | D | |---|----|----|----|----| | A | 0 | 7 | 9 | ∞ | | B | 7 | 0 | 10 | 15 | | C | 9 | 10 | 0 | 11 | | D | ∞ | 15 | 11 | 0 | 调用 `Kruskal(graph)` 可得输出： ``` Adding edge (A-B) with cost 7 Adding edge (A-C) with cost 9 Adding edge (C-D) with cost 11 Total minimum spanning tree cost is: 27 ``` ---