#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 **********/ }

以下是基于Kruskal算法实现最小生成树的C语言代码示例，其中包含了并查集的相关操作： ### Kruscal算法 C语言 实现 最小生成树 #### 定义结构体和全局变量 ```c #include <stdio.h> #include <stdlib.h> // 边的定义 typedef struct { int u; // 起点 int v; // 终点 int w; // 权重 } Edge; int n, m; // n表示顶点数，m表示边数 Edge edges[1000]; // 存储所有边 int father[1000]; // 并查集数组 ``` #### 初始化并查集 初始化每个节点的父亲为自己。 ```c void initUnionFind() { for (int i = 0; i < n; ++i) { father[i] = i; } } ``` #### 查找父亲节点（带路径压缩） ```c int findFather(int x) { if (father[x] != x) { father[x] = findFather(father[x]); } return father[x]; } ``` #### 合并两个集合 ```c void unionSet(int a, int b) { int faA = findFather(a); int faB = findFather(b); if (faA != faB) { // 如果不属于同一集合则合并 father[faA] = faB; } } ``` #### 排序函数比较器 按照权重升序排列边。 ```c int compare(const void *a, const void *b) { Edge *edge1 = (Edge *)a; Edge *edge2 = (Edge *)b; return edge1->w - edge2->w; } ``` #### 主逻辑：Kruskal算法 ```c long long kruskalMST() { qsort(edges, m, sizeof(Edge), compare); // 对边按权重排序 initUnionFind(); // 初始化并查集 long long totalWeight = 0; // 记录总权值 int countEdges = 0; // 已经加入的边数量 for (int i = 0; i < m && countEdges < n - 1; ++i) { int u = edges[i].u; int v = edges[i].v; int weight = edges[i].w; int fu = findFather(u); int fv = findFather(v); if (fu != fv) { // 不在同一集合中，可以加入 unionSet(u, v); // 合并两棵树 totalWeight += weight; // 加入总权值 countEdges++; // 增加已处理边的数量 } } if (countEdges == n - 1) { // 判断是否成功构建最小生成树 return totalWeight; } else { return -1; // 图不连通，无法构建最小生成树 } } ``` #### 输入与测试 ```c int main() { scanf("%d %d", &n, &m); // 输入顶点数和边数 for (int i = 0; i < m; ++i) { scanf("%d %d %d", &edges[i].u, &edges[i].v, &edges[i].w); // 输入每条边的信息 } long long result = kruskalMST(); if (result != -1) { printf("Minimum Spanning Tree Weight: %lld\n", result); // 输出最小生成树的总权值 } else { printf("No Minimum Spanning Tree exists.\n"); // 若不存在最小生成树 } return 0; } ``` 上述代码实现了Kruskal算法的核心部分，包括并查集的操作、边的排序以及逐步构建最小生成树的过程[^1][^2][^3][^4]。 --- 相关问题