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

一、上期回顾掌握 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; // 按权值升序排序 } }; vectorEdge 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; }3. 特点与复杂度基础版复杂度\(O(n^2)\)优势适合顶点少、边稠密的图优化可搭配优先队列堆优化为 \(O(m\log n)\)思路不变五、两大算法对比 选型口诀表格算法核心依赖复杂度适用场景Kruskal并查集 边排序\(O(m\log m)\)稀疏图边少点多刷题首选Prim邻接矩阵 / 堆\(O(n^2)\)稠密图边多点少选型口诀点少边多用 Prim点多边少用 Kruskal六、今日核心总结最小生成树连通全顶点、n-1 条边、总权值最小、无环路。Kruskal边排序 并查集判连通稀疏图首选。Prim以顶点为核心贪心拓展稠密图更合适。两个算法都基于贪心思想遇到不连通图直接判定无解。七、课后练习手写 Kruskal 完整代码结合并查集完成测试搭建稠密图使用 Prim 算法求解最小权值区分两种算法的使用场景