求图（邻接矩阵存储）最小生成树的克鲁斯卡尔#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 **********/ } （Kruska

### 克鲁斯卡尔算法实现最小生成树的逻辑解析 克鲁斯卡尔算法是一种基于贪心思想的最小生成树算法，其核心思想是按边的权值从小到大排序，逐步选择最小的边加入生成树中，同时确保不会形成环[^2]。以下是克鲁斯卡尔算法的核心步骤： 1. **初始化**：将所有顶点视为独立的连通分量。 2. **排序**：对图中的所有边按照权值从小到大进行排序[^3]。 3. **选取边**：依次检查每条边，如果该边连接的两个顶点不在同一个连通分量中，则将这条边加入生成树，并合并这两个顶点所在的连通分量[^4]。 4. **终止条件**：当生成树包含所有顶点时停止。 在C语言实现中，通常使用并查集（Union-Find）来判断和合并连通分量，以避免形成环。 --- ### C语言代码示例 以下是一个基于邻接矩阵存储的克鲁斯卡尔算法实现： ```c #include <stdio.h> #include <stdlib.h> #define MAX 100 #define INF 99999 // 并查集结构体 int parent[MAX]; // 查找函数，带路径压缩 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 rootX = find_set(x); int rootY = find_set(y); if (rootX != rootY) { parent[rootY] = rootX; } } // 边结构体 typedef struct { int u; int v; int weight; } Edge; // 比较函数，用于qsort排序 int compare(const void *a, const void *b) { Edge *edgeA = (Edge *)a; Edge *edgeB = (Edge *)b; return edgeA->weight - edgeB->weight; } // 克鲁斯卡尔算法主函数 void kruskal(int n, int edges_count, Edge edges[]) { // 初始化并查集 for (int i = 0; i < n; i++) { parent[i] = i; } // 对边按权值排序 qsort(edges, edges_count, sizeof(Edge), compare); int total_weight = 0; int count = 0; printf("Edges in the Minimum Spanning Tree:\n"); for (int i = 0; i < edges_count && count < n - 1; i++) { int u = edges[i].u; int v = edges[i].v; int weight = edges[i].weight; if (find_set(u) != find_set(v)) { // 检查是否形成环 union_set(u, v); // 合并连通分量 total_weight += weight; // 累加权值 count++; // 边计数 printf("(%d, %d) -> %d\n", u, v, weight); } } printf("Total Weight of MST: %d\n", total_weight); } int main() { int n = 5; // 顶点数 int edges_count = 7; // 边数 Edge edges[] = { {0, 1, 2}, {0, 3, 6}, {1, 2, 3}, {1, 3, 8}, {1, 4, 5}, {2, 4, 7}, {3, 4, 9} }; kruskal(n, edges_count, edges); return 0; } ``` --- ### 代码逻辑解析 1. **并查集初始化**： - 使用 `parent` 数组记录每个顶点所属的连通分量根节点，初始时每个顶点的父节点为自身[^4]。 2. **边排序**： - 使用 `qsort` 函数对所有边按权值从小到大排序[^3]。 3. **边选择与连通性检查**： - 对于每条边，调用 `find_set` 函数判断其两个顶点是否属于同一连通分量。 - 如果不属于同一连通分量，则调用 `union_set` 合并它们，并将该边加入生成树[^4]。 4. **终止条件**： - 当生成树包含 `n-1` 条边时，算法结束[^1]。 ---