当前位置：首页 > news >正文

Kruskal与Prim：最小生成树双雄对决

news 2026/5/29 23:59:17

一、上期回顾

掌握 Floyd 多源最短路算法，三层循环实现任意两点间最短路径，适配小规模图。今天学习最小生成树 (MST)，在连通图中选出边权和最小的连通子图，覆盖所有顶点且无环。

二、最小生成树基础概念

定义：给定连通无向带权图，选取 n-1 条边，连接全部 n 个顶点，且所有边权之和最小，该子树即为最小生成树。
核心性质：
- 包含图中所有顶点
- 恰好顶点数-1条边，无回路
- 总边权和全局最小
适用场景：城市修路、网络布线、管道铺设、集群组网等求最小成本问题。
主流两种实现：Kruskal 克鲁斯卡尔、Prim 普里姆

三、算法一：Kruskal 克鲁斯卡尔算法

1. 核心思想（贪心 + 并查集）

将所有边按权值从小到大排序
依次遍历每条边，用并查集判断两个顶点是否连通
不连通则选中这条边，合并两个集合；连通则跳过（避免成环）
选够n-1条边即可结束

2. 完整代码模板

#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N = 1005; // 边结构体：起点u、终点v、权值w struct Edge { int u, v, w; bool operator<(const Edge& e) const { return w < e.w; // 按权值升序排序 } }; vector<Edge> edges; int parent[N]; // 并查集父节点数组 int n, m; // n顶点数，m边数 // 并查集初始化 void init() { for(int i = 1; i <= n; ++i) parent[i] = i; } // 查找+路径压缩 int find(int x) { if(parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } // Kruskal 算法，返回最小生成树总权值 int kruskal() { init(); sort(edges.begin(), edges.end()); // 边排序 int sum = 0; // 总权值 int cnt = 0; // 已选边数 for(auto& e : edges) { int fu = find(e.u); int fv = find(e.v); if(fu != fv) { parent[fv] = fu; sum += e.w; cnt++; if(cnt == n - 1) // 选够n-1条边，提前退出 break; } } // 未选够边数，说明图不连通，无生成树 if(cnt < n - 1) return -1; return sum; } int main() { cin >> n >> m; edges.resize(m); for(int i = 0; i < m; ++i) { cin >> edges[i].u >> edges[i].v >> edges[i].w; } int res = kruskal(); if(res == -1) cout << "图不连通，无法生成最小生成树" << endl; else cout << "最小生成树总权值：" << res << endl; return 0; }

3. 特点与复杂度

复杂度：\(O(m\log m)\)，主要耗时在边排序
优势：适合边稀疏的图（边数远小于顶点数），代码简洁
依赖：必须配合并查集判断连通性、防环

四、算法二：Prim 普里姆算法

1. 核心思想（贪心 + 邻接矩阵 / 邻接表）

维护两个集合：已加入生成树的顶点集合、未加入集合
每次选取连接两个集合、权值最小的边，将对应顶点加入树中
重复 n-1 次，直到所有顶点加入

2. 邻接矩阵版模板（适合小规模图）

#include <iostream> #include <cstring> #include <climits> using namespace std; const int N = 1005; const int INF = 0x3f3f3f3f; int graph[N][N]; // 邻接矩阵存图 int dist[N]; // 未选点到生成树的最短距离 bool vis[N]; // 标记是否已加入生成树 int n, m; int prim() { memset(vis, false, sizeof(vis)); // 初始化距离数组 for(int i = 1; i <= n; ++i) dist[i] = graph[1][i]; vis[1] = true; // 从1号顶点开始 int sum = 0; for(int i = 1; i < n; ++i) // 还需选n-1个点 { // 找距离最小的未访问点 int minVal = INF; int pos = -1; for(int j = 1; j <= n; ++j) { if(!vis[j] && dist[j] < minVal) { minVal = dist[j]; pos = j; } } if(pos == -1) return -1; // 图不连通 sum += minVal; vis[pos] = true; // 更新剩余点到生成树的最短距离 for(int j = 1; j <= n; ++j) { if(!vis[j] && graph[pos][j] < dist[j]) dist[j] = graph[pos][j]; } } return sum; } int main() { // 矩阵初始化 memset(graph, 0x3f, sizeof(graph)); cin >> n >> m; for(int i = 1; i <= n; ++i) graph[i][i] = 0; for(int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; // 无向图双向赋值，重边取最小值 if(w < graph[u][v]) { graph[u][v] = w; graph[v][u] = w; } } int res = prim(); if(res == -1) cout << "图不连通" << endl; else cout << "最小生成树总权值：" << res << endl; return 0; }