本文献给：
已掌握图论基础，希望理解如何在带权连通图中找到最小生成树的C语言学习者。本文将系统讲解两种经典的最小生成树算法。
你将学到：
- 最小生成树问题的定义与核心概念
- Prim算法：从顶点出发，逐步扩张生成树
- Kruskal算法：按边权排序，逐步合并连通分量
- 算法对比与实战应用
@toc
第一部分：问题定义与核心概念
1. 什么是最小生成树？
在带权连通无向图G=(V,E,w)G = (V, E, w)G=(V,E,w)中，w:E→Rw: E \rightarrow \mathbb{R}w:E→R为边权函数。生成树是GGG的一个子图，它是一棵包含GGG中所有顶点的树。最小生成树是所有生成树中边权之和最小的生成树。
关键术语：
- 连通图：图中任意两个顶点都有路径相连。
- 生成树：包含所有顶点的树，有∣V∣−1|V|-1∣V∣−1条边。
- 边权：通常为非负实数，表示距离、成本等。
- 最小生成树性质：最小生成树不一定唯一，但边权之和唯一。
第二部分：图的存储（带权图）
与最短路径相同，我们使用带权图的存储方式。
#defineMAX_V100#defineINF0x3f3f3f3f// 表示"无穷大"的一个较大数值// 邻接矩阵（带权）typedefstruct{intmatrix[MAX_V][MAX_V];// 存储权值，INF表示无边intvertex_count;}GraphMatrixWeighted;voidinit_graph_weighted(GraphMatrixWeighted*g,intn){g->vertex_count=n;for(inti=0;i<n;i++){for(intj=0;j<n;j++){g->matrix[i][j]=(i==j)?0:INF;// 自身距离为0，但生成树中不考虑自环}}}voidadd_edge_weighted(GraphMatrixWeighted*g,intu,intv,intweight){if(u>=g->vertex_count||v>=g->vertex_count)return;g->matrix[u][v]=weight;g->matrix[v][u]=weight;// 无向图}第三部分：Prim算法
1. 核心思想
贪心策略。从任意一个顶点开始，每次选择连接已选顶点集合和未选顶点集合的最小权值边，并将该边连接的未选顶点加入已选集合。直到所有顶点都被选中。
算法正确性依赖：最小生成树的局部最优选择性质。
2. 算法步骤（朴素O(∣V∣2)O(|V|^2)O(∣V∣2)实现）
- 初始化：选择一个起始顶点，设置
visited[src]=1，初始化min_edge[v]为从起始顶点到v的边权（无边则为INF）。 - 循环
|V|-1次：
a. 从未访问的顶点中选择min_edge值最小的顶点u。
b. 将顶点u加入生成树（标记visited[u]=1），累加生成树权重。
c. 更新min_edge数组：对于每个未访问的顶点v，如果matrix[u][v] < min_edge[v]，则更新min_edge[v] = matrix[u][v]。 - 循环结束，得到最小生成树的总权重。
3. C语言实现
// Prim算法 (邻接矩阵，朴素实现)intprim(GraphMatrixWeighted*g){intvisited[MAX_V]={0};intmin_edge[MAX_V];// 记录当前已选顶点集合到未选顶点的最小边权inttotal_weight=0;// 初始化，从顶点0开始visited[0]=1;for(inti=0;i<g->vertex_count;i++){min_edge[i]=g->matrix[0][i];}// 还需要选择 |V|-1 个顶点for(intcount=1;count<g->vertex_count;count++){// 找到未访问的顶点中 min_edge 最小的顶点intu=-1;intmin_weight=INF;for(intv=0;v<g->vertex_count;v++){if(!visited[v]&&min_edge[v]<min_weight){min_weight=min_edge[v];u=v;}}if(u==-1){// 图不连通，无法形成生成树return-1;}visited[u]=1;total_weight+=min_weight;// 更新 min_edge 数组for(intv=0;v<g->vertex_count;v++){if(!visited[v]&&g->matrix[u][v]<min_edge[v]){min_edge[v]=g->matrix[u][v];}}}returntotal_weight;}算法复杂度：
- 时间复杂度：O(∣V∣2)O(|V|^2)O(∣V∣2)，适合稠密图。
- 空间复杂度：O(∣V∣)O(|V|)O(∣V∣)。
- 优化方向：使用**优先队列（最小堆）**可将时间复杂度降为O((∣V∣+∣E∣)log∣V∣)O((|V|+|E|) \log |V|)O((∣V∣+∣E∣)log∣V∣)，适合稀疏图。
第四部分：Kruskal算法
1. 核心思想
贪心策略。将图中的所有边按权值从小到大排序，然后从权值最小的边开始，如果这条边连接的两个顶点不在同一个连通分量中，则选择这条边，并将两个连通分量合并。直到选择了∣V∣−1|V|-1∣V∣−1条边。
算法正确性依赖：最小生成树的全局最优选择性质。
2. 算法步骤
- 将图中所有边按权值从小到大排序。
- 初始化一个并查集，每个顶点自成一个集合。
- 依次考察每条边（按权值从小到大）：
- 如果该边连接的两个顶点属于不同的集合（即不连通），则选择该边，并将两个集合合并。
- 如果属于同一个集合，则选择这条边会形成环，因此舍弃。
- 当选择的边数达到∣V∣−1|V|-1∣V∣−1时，算法结束。
3. 并查集（Disjoint Set）辅助数据结构
Kruskal算法需要并查集来快速判断两个顶点是否属于同一个连通分量。
// 并查集实现typedefstruct{intparent[MAX_V];intrank[MAX_V];}DisjointSet;voidmake_set(DisjointSet*ds,intn){for(inti=0;i<n;i++){ds->parent[i]=i;ds->rank[i]=0;}}intfind(DisjointSet*ds,intx){if(ds->parent[x]!=x){ds->parent[x]=find(ds,ds->parent[x]);// 路径压缩}returnds->parent[x];}voidunion_set(DisjointSet*ds,intx,inty){introot_x=find(ds,x);introot_y=find(ds,y);if(root_x!=root_y){// 按秩合并if(ds->rank[root_x]<ds->rank[root_y]){ds->parent[root_x]=root_y;}elseif(ds->rank[root_x]>ds->rank[root_y]){ds->parent[root_y]=root_x;}else{ds->parent[root_y]=root_x;ds->rank[root_x]++;}}}4. Kruskal算法实现
为了便于操作，我们使用边列表来存储图。
// 边结构体typedefstruct{intu,v;intweight;}Edge;// 图（边列表）typedefstruct{Edge edges[MAX_V*MAX_V];intedge_count;intvertex_count;}GraphEdgeList;// 比较函数，用于排序intcompare_edges(constvoid*a,constvoid*b){Edge*edge_a=(Edge*)a;Edge*edge_b=(Edge*)b;returnedge_a->weight-edge_b->weight;}// Kruskal算法intkruskal(GraphEdgeList*g){// 1. 将边按权值排序qsort(g->edges,g->edge_count,sizeof(Edge),compare_edges);// 2. 初始化并查集DisjointSet ds;make_set(&ds,g->vertex_count);inttotal_weight=0;intedges_selected=0;// 3. 遍历每条边for(inti=0;i<g->edge_count;i++){intu=g->edges[i].u;intv=g->edges[i].v;intweight=g->edges[i].weight;// 如果u和v不在同一个集合中if(find(&ds,u)!=find(&ds,v)){union_set(&ds,u,v);total_weight+=weight;edges_selected++;if(edges_selected==g->vertex_count-1){break;}}}// 如果选出的边数不足 |V|-1，则图不连通if(edges_selected!=g->vertex_count-1){return-1;}returntotal_weight;}算法复杂度：
- 时间复杂度：O(∣E∣log∣E∣)O(|E| \log |E|)O(∣E∣log∣E∣)，主要开销在排序。
- 空间复杂度：O(∣V∣+∣E∣)O(|V| + |E|)O(∣V∣+∣E∣)。
第五部分：总结与对比
算法对比表
| 特性 | Prim算法 | Kruskal算法 |
|---|---|---|
| 适用图类型 | 连通图（通常稠密图） | 连通图（通常稀疏图） |
| 核心思想 | 从顶点出发，逐步扩张生成树 | 按边权排序，逐步合并连通分量 |
| 时间复杂度 | O(∣V∣2)O(|V|^2)O(∣V∣2)或O((∣V∣+∣E∣)log∣V∣)O((|V|+|E|)\log|V|)O((∣V∣+∣E∣)log∣V∣) | O(∣E∣log∣E∣)O(|E|\log|E|)O(∣E∣log∣E∣) |
| 空间复杂度 | O(∣V∣)O(|V|)O(∣V∣) | O(∣V∣+∣E∣)O(|V|+|E|)O(∣V∣+∣E∣) |
| 优点 | 适合稠密图，实现简单 | 适合稀疏图，边排序后操作简单 |
| 缺点 | 稠密图时效率高，稀疏图不如Kruskal | 稀疏图时效率高，稠密图排序开销大 |
| 存储结构 | 邻接矩阵或邻接表 | 边列表 |
选择指南
- 稠密图：优先使用Prim算法（朴素实现即可）。
- 稀疏图：优先使用Kruskal算法，因为其时间复杂度与边数有关，排序开销相对较小。
- 图存储结构：如果图本身是边列表形式，使用Kruskal算法更方便；如果是邻接矩阵或邻接表，Prim算法可能更方便。
觉得文章有帮助？别忘了：
👍 点赞 👍- 给我一点鼓励
⭐ 收藏 ⭐- 方便以后查看
🔔 关注 🔔- 获取更新通知
标签：#C语言#图论#最小生成树#Prim算法#Kruskal算法#算法
