C语言图论：最小生成树算法

本文献给：
已掌握图论基础，希望理解如何在带权连通图中找到最小生成树的C语言学习者。本文将系统讲解两种经典的最小生成树算法。

你将学到：

1. 最小生成树问题的定义与核心概念
2. Prim算法：从顶点出发，逐步扩张生成树
3. Kruskal算法：按边权排序，逐步合并连通分量
4. 算法对比与实战应用

@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)实现）

1. 初始化：选择一个起始顶点，设置visited[src]=1，初始化min_edge[v]为从起始顶点到v的边权（无边则为INF）。
2. 循环|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. 循环结束，得到最小生成树的总权重。

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. 算法步骤

1. 将图中所有边按权值从小到大排序。
2. 初始化一个并查集，每个顶点自成一个集合。
3. 依次考察每条边（按权值从小到大）：
   • 如果该边连接的两个顶点属于不同的集合（即不连通），则选择该边，并将两个集合合并。
   • 如果属于同一个集合，则选择这条边会形成环，因此舍弃。
4. 当选择的边数达到∣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∣)。

第五部分：总结与对比

算法对比表

选择指南

1. 稠密图：优先使用Prim算法（朴素实现即可）。
2. 稀疏图：优先使用Kruskal算法，因为其时间复杂度与边数有关，排序开销相对较小。
3. 图存储结构：如果图本身是边列表形式，使用Kruskal算法更方便；如果是邻接矩阵或邻接表，Prim算法可能更方便。

觉得文章有帮助？别忘了：
👍 点赞 👍- 给我一点鼓励
⭐ 收藏 ⭐- 方便以后查看
🔔 关注 🔔- 获取更新通知

标签：#C语言#图论#最小生成树#Prim算法#Kruskal算法#算法