一、算法描述
克鲁斯卡尔算法是求解无向带权连通图的最小生成树（MST） 的经典算法，核心思想是 “按权值从小到大选边，避免形成环，直到连通所有顶点”，具体步骤：
-
数据准备：将图中的所有边存储为边集（包含两个顶点和权值），并初始化并查集（用于跟踪连通分量）。
-
边排序：将所有边按权值从小到大排序，确保每次优先选择权值最小的边。
-
选边与合并
：遍历排序后的边，对每条边：
- 用并查集的
Find操作判断边的两个顶点是否属于同一连通分量（若属于同一分量，加入该边会形成环，需跳过）； - 若不属于同一分量，将该边加入最小生成树，并通过
Union操作合并两个顶点的连通分量；
- 用并查集的
-
终止条件：当加入的边数达到
n-1（n为顶点数）时，算法结束（此时已形成包含所有顶点的最小生成树）。
二、代码
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
#define MAX_EDGE_NUM 100 // 最大边数
// 边的结构（存储顶点对和权值）
typedef struct {
int u, v; // 边的两个顶点（下标）
int weight; // 边的权值
} Edge;
// 图的结构（基于边集存储，适合克鲁斯卡尔算法）
typedef struct {
char vertices[MAX_VERTEX_NUM]; // 顶点信息
Edge edges[MAX_EDGE_NUM]; // 边集
int vexnum, arcnum; // 顶点数、边数
} MGraph;
// 并查集（用于判断连通分量）
typedef struct {
int parent[MAX_VERTEX_NUM]; // 父节点数组（-1表示根节点）
int rank[MAX_VERTEX_NUM]; // 秩（用于优化合并）
} UnionFind;
// 初始化并查集
void InitUnionFind(UnionFind *uf, int n) {
for (int i = 0; i < n; i++) {
uf->parent[i] = -1; // 初始每个顶点都是自己的根
uf->rank[i] = 0; // 秩初始为0
}
}
// 查找根节点（带路径压缩）
int Find(UnionFind *uf, int x) {
if (uf->parent[x] != -1) {
// 递归压缩路径：让x的父节点直接指向根
uf->parent[x] = Find(uf, uf->parent[x]);
}
return x;
}
// 合并两个集合（按秩合并）
void Union(UnionFind *uf, int x, int y) {
int x_root = Find(uf, x);
int y_root = Find(uf, y);
if (x_root == y_root) return; // 已在同一集合
// 秩小的树合并到秩大的树的根下
if (uf->rank[x_root] < uf->rank[y_root]) {
uf->parent[x_root] = y_root;
} else {
uf->parent[y_root] = x_root;
if (uf->rank[x_root] == uf->rank[y_root]) {
uf->rank[x_root]++; // 秩相等时，合并后根的秩+1
}
}
}
// 交换两条边（用于排序）
void SwapEdge(Edge *a, Edge *b) {
Edge temp = *a;
*a = *b;
*b = temp;
}
// 对边按权值从小到大排序（简单选择排序，便于理解）
void SortEdges(Edge edges[], int n) {
for (int i = 0; i < n-1; i++) {
int min_idx = i;
for (int j = i+1; j < n; j++) {
if (edges[j].weight < edges[min_idx].weight) {
min_idx = j;
}
}
SwapEdge(&edges[i], &edges[min_idx]);
}
}
/**
* @brief 克鲁斯卡尔算法求最小生成树
* 算法描述：
* 1. 初始化并查集，用于管理连通分量；
* 2. 将图中所有边按权值从小到大排序；
* 3. 遍历排序后的边，对每条边(u, v)：
* a. 用Find判断u和v是否在同一连通分量；
* b. 若不在，将该边加入最小生成树，并通过Union合并u和v的连通分量；
* c. 若已加入n-1条边（n为顶点数），终止循环（生成树已完成）。
*/
void Kruskal(MGraph G) {
UnionFind uf;
InitUnionFind(&uf, G.vexnum); // 初始化并查集
SortEdges(G.edges, G.arcnum); // 边按权值排序
int count = 0; // 记录已加入生成树的边数
printf("\n最小生成树的边（u, v, 权值）：\n");
for (int i = 0; i < G.arcnum; i++) {
int u = G.edges[i].u;
int v = G.edges[i].v;
int w = G.edges[i].weight;
int root_u = Find(&uf, u);
int root_v = Find(&uf, v);
if (root_u != root_v) { // 不在同一连通分量，加入生成树
printf("(%c, %c, %d)\n", G.vertices[u], G.vertices[v], w);
Union(&uf, u, v);
count++;
if (count == G.vexnum - 1) break; // 生成树已包含所有顶点
}
}
if (count < G.vexnum - 1) {
printf("图不连通，无法生成最小生成树！\n");
}
}
int main() {
// 构建测试图（4个顶点A、B、C、D，5条边）
MGraph G;
G.vexnum = 4;
G.arcnum = 5;
G.vertices[0] = 'A'; // 顶点0:A
G.vertices[1] = 'B'; // 顶点1:B
G.vertices[2] = 'C'; // 顶点2:C
G.vertices[3] = 'D'; // 顶点3:D
// 初始化边集（u, v, weight）
G.edges[0] = {0, 1, 2}; // A-B, 权2
G.edges[1] = {0, 2, 3}; // A-C, 权3
G.edges[2] = {1, 2, 1}; // B-C, 权1
G.edges[3] = {1, 3, 4}; // B-D, 权4
G.edges[4] = {2, 3, 5}; // C-D, 权5
// 打印图的边信息
printf("图的所有边（u, v, 权值）：\n");
for (int i = 0; i < G.arcnum; i++) {
printf("(%c, %c, %d)\n",
G.vertices[G.edges[i].u],
G.vertices[G.edges[i].v],
G.edges[i].weight);
}
// 执行克鲁斯卡尔算法
Kruskal(G);
return 0;
}
三、时空复杂度分析（Markdown格式）
时间复杂度
边排序：对 E条边排序，时间复杂度为 O(E \log E)（代码中用选择排序，实际优化可用快速排序，此处按标准优化后分析）
并查集操作：Find（带路径压缩）和 Union（按秩合并）的时间复杂度接近 O(1)（严格为 O(\alpha(V))，\alpha 是反阿克曼函数，增长极慢），总操作次数为 O(E)；
总时间复杂度：由排序主导，为 \boxed{O(E \log E)}（E 为边数，V 为顶点数）。
空间复杂度
- 边集存储：需要 O(E) 空间存储所有边；
- 并查集：父节点数组和秩数组共需 O(V) 空间；
- 总空间复杂度： \boxed{O(E + V)}。
评论区