目录一、前置知识什么是最小生成树二、Kruskal 算法“边”贪心稀疏图首选1. 核心思想2. 算法步骤3. 完整代码 逐行注释4. 算法优缺点三、Prim 算法“点”贪心稠密图首选1. 核心思想2. 算法步骤3. 完整代码 逐行注释4. 算法优缺点四、两大算法核心对比面试 / 做题必背五、做题小技巧六、总结关键点回顾最小生成树Minimum Spanning TreeMST是图论中最经典的算法之一核心作用是在一个带权无向连通图中选出 n-1 条边连接所有 n 个节点且总边权最小不形成环。本文将带你吃透最小生成树的两大核心算法✅ Kruskal 算法并查集 贪心适合稀疏图✅ Prim 算法贪心 遍历适合稠密图附带可直接运行的 C 模板 详细注释 场景对比新手也能轻松掌握一、前置知识什么是最小生成树举个生活例子你要给 n 个村庄修公路任意两个村庄之间修公路的成本不同要求所有村庄连通、总修路成本最低、不修环路浪费钱最终修出来的公路网就是这个图的最小生成树。核心性质包含图中所有 n 个节点有且仅有n-1 条边总边权最小无环、连通这也是最小生成树名字的由来只需保证联通无需任意两点间都有路树在这基础上选择成本最低的方案最小但是要注意在实际应用中生成树是成本最小不代表最短在实际中我们要兼顾路程和成本比如贵州花江峡谷大桥可能不是联通两地成本最低的方案但是建造之后所带来的效益却是远超其他方案算法不要死学学的是计算机思维二、Kruskal 算法“边”贪心稀疏图首选1. 核心思想对边进行操作图中的边权最小的边定然是生成树的一条枝干这便是Kruskal 算法最核心的贪心思想对边从小到大遍历只要边所连的两点不在同一个联通块就保留这条边最终选择n-1条边节点数为n的树边为n-1一句话总结小边优先并查集判环2. 算法步骤把图中所有边按权值升序排列使用优先队列贼方便初始化并查集每个节点自己是一个连通块遍历排序后的边若边的两个端点不属于同一连通块 → 选中这条边合并连通块若属于同一连通块 → 跳过会成环选中 n-1 条边时结束算法3. 完整代码 逐行注释P3366 【模板】最小生成树https://www.luogu.com.cn/problem/P3366#include bits/stdc.h using namespace std; #define int long long const int N 2e6 10; const int inf 2147483647; // 边的结构体存储两个端点边权 struct edge { int x, y, z; }; // 优先队列比较器小顶堆边权小的优先出队 struct cmp { bool operator()(const edge e1, const edge e2) { return e1.z e2.z; } }; int fa[N]; // 并查集父节点数组 int n, m; // n节点数m边数 int sum, cnt; // sum最小生成树总权值cnt已选边数 priority_queueedge, vectoredge, cmp q; // 存储所有边 // 并查集初始化每个节点的父节点是自己 void init(){ for(int i 0; i n; i) fa[i] i; } // 并查集查找 int get(int x){ return fa[x] (fa[x] x ? x : get(fa[x])); } // 合并两个连通块a挂在b上 void merge(int a, int b){ fa[get(a)] get(b); } // Kruskal算法核心 void kruskal() { while (!q.empty() cnt n-1) { edge t q.top(); q.pop(); // 取出当前最小边 int x t.x, y t.y, z t.z; // 两个节点不在同一连通块 → 选中这条边 if (get(x) ! get(y)) { sum z; // 累加总权值 merge(x, y); // 合并连通块 cnt; // 已选边数1 } } // 最终判断是否连通选够n-1条边 if (cnt n-1) cout sum endl; else cout orz endl; // 图不连通无生成树 } void solve() { cin n m; init(); sum 0, cnt 0; // 初始化变量 for (int i 0; i m; i) { int x, y, z; cin x y z; q.push({x, y, z}); // 边存入优先队列 } kruskal(); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }4. 算法优缺点通过上面的讲解大家应该看出来了Kruskal 算法一直都是在对边进行操作故而✅ 优点代码简洁、易理解、稀疏图效率高边少的图❌ 缺点需要存储所有边稠密图边多效率略低时间复杂度O(mlogm)m 为边数主要耗时在排序三、Prim 算法“点”贪心稠密图首选1. 核心思想核心贪心思想和Kruskal 算法差不多只不过Prim算法是对点进行操作Prim需要抽象出两个集合集合1已选节点集合也就是已经确定是树的一部分集合2未选节点集合待成树每次选2到1的最小边权将对应节点加入集合直到所有节点都被选中。我们不用在意具体两点间的边权考虑的是点到集合1的最短距离看后面代码理解一句话总结点集扩张每次选最短跨集边。2. 算法步骤初始化选定一个起点如节点 1标记为已选维护数组d[]d[i]表示节点 i 到已选点集的最小距离循环 n-1 次需要选 n-1 条边找到未选节点中d[]最小的节点加入已选集合累加边权更新其他未选节点的d[]值所有节点加入后结束算法3. 完整代码 逐行注释P3366 【模板】最小生成树https://www.luogu.com.cn/problem/P3366朴素版#include bits/stdc.h using namespace std; #define int long long const int N 2e6 10; const int inf 2147483647; // 邻接表节点存储终点边权 struct node { int u, w; }; bool st[N]; // 标记节点是否已加入生成树 vectornode mp[N]; // 邻接表存储图 int d[N]; // d[i]节点i到已选点集的最小距离 int n, m, sum; // sum最小生成树总权值 // Prim算法核心 void prim() { d[1] 0; // 从节点1开始初始距离为0 st[1] true; // 标记节点1已选 // 初始化起点的邻接节点距离 for (auto x : mp[1]) d[x.u] min(d[x.u], x.w); // 选n-1条边循环n-1次 for (int i 2; i n; i) { int mn inf, xb -1; // 找到未选节点中d[]最小的节点 for (int j 2; j n; j) { if (!st[j] d[j] mn) { mn d[j]; xb j; } } // 无符合条件的节点 → 图不连通直接结束即可 if (xb -1) { sum inf; return; } st[xb] true; // 标记节点已选 sum mn; // 累加总权值 // 更新邻接节点的最小距离 for (auto x : mp[xb]) { d[x.u] min(d[x.u], x.w); } } } void solve() { cin n m; for (int i 0; i m; i) { int x, y, z; cin x y z; mp[x].push_back({y, z}); // 无向图双向存边 mp[y].push_back({x, z}); } // 初始化距离数组为无穷大 for (int i 1; i n; i) d[i] inf; sum 0; prim(); if (sum inf) cout orz endl; else cout sum endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }堆优化版#include bits/stdc.h using namespace std; #define int long long const int N 2e6 10; const int inf 2147483647; // 无穷大 // 邻接表存储边u是终点w是边权 struct node { int u, w; }; // 堆节点存储【当前节点到生成树的最小距离】【节点编号】 struct HeapNode { int dis, id; // 小根堆重载让优先队列从小到大弹出距离越小越优先 bool operator(const HeapNode other) const { return dis other.dis; } }; bool st[N]; // 标记节点是否已经加入最小生成树 vectornode mp[N];// 邻接表存图 int d[N]; // d[i]节点i到已选生成树的最小边权 int n, m, sum; // n点数m边数sum生成树总权值 void prim() { // 1. 初始化所有节点到生成树的距离设为无穷大 for (int i 1; i n; i) d[i] inf; // 初始化所有节点未被访问 memset(st, 0, sizeof st); sum 0; // 总权值归零 d[1] 0; // 从 1 号节点开始初始距离为 0 // 小根堆每次取出【距离最小】的节点 priority_queueHeapNode q; q.push({0, 1}); // 将起点距离0编号1推入堆 int cnt 0; // 记录已经加入生成树的节点数量 // 2. 开始循环堆不为空就继续 while (!q.empty()) { // 取出堆顶当前距离最小的节点 auto now q.top(); q.pop(); int u now.id; // 当前节点编号 int dis now.dis;// 当前节点到生成树的最小距离 // 3. 重要剪枝如果这个节点已经加入过生成树直接跳过堆里的旧数据 if (st[u]) continue; // 4. 标记该节点已加入生成树 st[u] true; sum dis; // 累加这条边的权值 cnt; // 已加入节点数 1 // 5. 遍历当前节点的所有邻边松弛操作 for (auto edge : mp[u]) { int v edge.u; // 邻接点编号 int w edge.w; // 这条边的权值 // 6. 如果邻接点没被选过且新边权更小 → 更新距离 if (!st[v] d[v] w) { d[v] w; // 更新最小距离 q.push({d[v], v}); // 新状态推入堆 } } } // 7. 最终判断如果加入的节点数 ! 总点数 → 图不连通 if (cnt ! n) sum inf; } void solve() { cin n m; // 读入 m 条无向边存入邻接表 for (int i 0; i m; i) { int x, y, z; cin x y z; mp[x].push_back({y, z}); mp[y].push_back({x, z}); } // 执行堆优化 Prim prim(); // 输出答案不连通输出 orz否则输出总权值 if (sum inf) cout orz\n; else cout sum \n; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }4. 算法优缺点与Kruskal 算法一直都是在对边进行操作相对Prim一直在对点进行操作故而✅ 优点稠密图效率极高边多、节点少的图无需存储所有边❌ 缺点朴素版代码理解难度略高于 Kruskal时间复杂度朴素版O(n2)堆优化版O(mlogn)n 为节点数四、两大算法核心对比面试 / 做题必背维度Kruskal 算法Prim 算法核心思路边贪心从小到大选边点贪心扩张点集数据结构优先队列 / 排序 并查集邻接表 距离数组判环方式并查集判断连通块无需判环点集天然无环适用场景稀疏图边少m 远小于 n²稠密图边多m 接近 n²代码难度简单新手首选中等时间复杂度O(mlogm)朴素版O(n2)五、做题小技巧稀疏图无脑用 Kruskal代码短不易错稠密图用 Prim 朴素版效率拉满数据范围节点数≤1e4 用 Prim边数≤1e6 用 Kruskal六、总结最小生成树的本质就是贪心Kruskal选最小的边不环就留靠并查集实现Prim扩最小的点逐步连通靠距离数组实现。关键点回顾最小生成树连通所有节点、n-1 条边、总权最小、无环Kruskal边排序 并查集稀疏图首选O(mlogm)Prim点集扩张 距离数组稠密图首选O(n2)核心都是贪心根据图的疏密选择算法即可本篇文章主要介绍两个最小生成树算法里面有一些比如优先队列的重载并没有讲后续还会写专门介绍优先队列使用方法
最小生成树算法
发布时间：2026/5/26 19:14:48
目录一、前置知识什么是最小生成树二、Kruskal 算法“边”贪心稀疏图首选1. 核心思想2. 算法步骤3. 完整代码 逐行注释4. 算法优缺点三、Prim 算法“点”贪心稠密图首选1. 核心思想2. 算法步骤3. 完整代码 逐行注释4. 算法优缺点四、两大算法核心对比面试 / 做题必背五、做题小技巧六、总结关键点回顾最小生成树Minimum Spanning TreeMST是图论中最经典的算法之一核心作用是在一个带权无向连通图中选出 n-1 条边连接所有 n 个节点且总边权最小不形成环。本文将带你吃透最小生成树的两大核心算法✅ Kruskal 算法并查集 贪心适合稀疏图✅ Prim 算法贪心 遍历适合稠密图附带可直接运行的 C 模板 详细注释 场景对比新手也能轻松掌握一、前置知识什么是最小生成树举个生活例子你要给 n 个村庄修公路任意两个村庄之间修公路的成本不同要求所有村庄连通、总修路成本最低、不修环路浪费钱最终修出来的公路网就是这个图的最小生成树。核心性质包含图中所有 n 个节点有且仅有n-1 条边总边权最小无环、连通这也是最小生成树名字的由来只需保证联通无需任意两点间都有路树在这基础上选择成本最低的方案最小但是要注意在实际应用中生成树是成本最小不代表最短在实际中我们要兼顾路程和成本比如贵州花江峡谷大桥可能不是联通两地成本最低的方案但是建造之后所带来的效益却是远超其他方案算法不要死学学的是计算机思维二、Kruskal 算法“边”贪心稀疏图首选1. 核心思想对边进行操作图中的边权最小的边定然是生成树的一条枝干这便是Kruskal 算法最核心的贪心思想对边从小到大遍历只要边所连的两点不在同一个联通块就保留这条边最终选择n-1条边节点数为n的树边为n-1一句话总结小边优先并查集判环2. 算法步骤把图中所有边按权值升序排列使用优先队列贼方便初始化并查集每个节点自己是一个连通块遍历排序后的边若边的两个端点不属于同一连通块 → 选中这条边合并连通块若属于同一连通块 → 跳过会成环选中 n-1 条边时结束算法3. 完整代码 逐行注释P3366 【模板】最小生成树https://www.luogu.com.cn/problem/P3366#include bits/stdc.h using namespace std; #define int long long const int N 2e6 10; const int inf 2147483647; // 边的结构体存储两个端点边权 struct edge { int x, y, z; }; // 优先队列比较器小顶堆边权小的优先出队 struct cmp { bool operator()(const edge e1, const edge e2) { return e1.z e2.z; } }; int fa[N]; // 并查集父节点数组 int n, m; // n节点数m边数 int sum, cnt; // sum最小生成树总权值cnt已选边数 priority_queueedge, vectoredge, cmp q; // 存储所有边 // 并查集初始化每个节点的父节点是自己 void init(){ for(int i 0; i n; i) fa[i] i; } // 并查集查找 int get(int x){ return fa[x] (fa[x] x ? x : get(fa[x])); } // 合并两个连通块a挂在b上 void merge(int a, int b){ fa[get(a)] get(b); } // Kruskal算法核心 void kruskal() { while (!q.empty() cnt n-1) { edge t q.top(); q.pop(); // 取出当前最小边 int x t.x, y t.y, z t.z; // 两个节点不在同一连通块 → 选中这条边 if (get(x) ! get(y)) { sum z; // 累加总权值 merge(x, y); // 合并连通块 cnt; // 已选边数1 } } // 最终判断是否连通选够n-1条边 if (cnt n-1) cout sum endl; else cout orz endl; // 图不连通无生成树 } void solve() { cin n m; init(); sum 0, cnt 0; // 初始化变量 for (int i 0; i m; i) { int x, y, z; cin x y z; q.push({x, y, z}); // 边存入优先队列 } kruskal(); } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }4. 算法优缺点通过上面的讲解大家应该看出来了Kruskal 算法一直都是在对边进行操作故而✅ 优点代码简洁、易理解、稀疏图效率高边少的图❌ 缺点需要存储所有边稠密图边多效率略低时间复杂度O(mlogm)m 为边数主要耗时在排序三、Prim 算法“点”贪心稠密图首选1. 核心思想核心贪心思想和Kruskal 算法差不多只不过Prim算法是对点进行操作Prim需要抽象出两个集合集合1已选节点集合也就是已经确定是树的一部分集合2未选节点集合待成树每次选2到1的最小边权将对应节点加入集合直到所有节点都被选中。我们不用在意具体两点间的边权考虑的是点到集合1的最短距离看后面代码理解一句话总结点集扩张每次选最短跨集边。2. 算法步骤初始化选定一个起点如节点 1标记为已选维护数组d[]d[i]表示节点 i 到已选点集的最小距离循环 n-1 次需要选 n-1 条边找到未选节点中d[]最小的节点加入已选集合累加边权更新其他未选节点的d[]值所有节点加入后结束算法3. 完整代码 逐行注释P3366 【模板】最小生成树https://www.luogu.com.cn/problem/P3366朴素版#include bits/stdc.h using namespace std; #define int long long const int N 2e6 10; const int inf 2147483647; // 邻接表节点存储终点边权 struct node { int u, w; }; bool st[N]; // 标记节点是否已加入生成树 vectornode mp[N]; // 邻接表存储图 int d[N]; // d[i]节点i到已选点集的最小距离 int n, m, sum; // sum最小生成树总权值 // Prim算法核心 void prim() { d[1] 0; // 从节点1开始初始距离为0 st[1] true; // 标记节点1已选 // 初始化起点的邻接节点距离 for (auto x : mp[1]) d[x.u] min(d[x.u], x.w); // 选n-1条边循环n-1次 for (int i 2; i n; i) { int mn inf, xb -1; // 找到未选节点中d[]最小的节点 for (int j 2; j n; j) { if (!st[j] d[j] mn) { mn d[j]; xb j; } } // 无符合条件的节点 → 图不连通直接结束即可 if (xb -1) { sum inf; return; } st[xb] true; // 标记节点已选 sum mn; // 累加总权值 // 更新邻接节点的最小距离 for (auto x : mp[xb]) { d[x.u] min(d[x.u], x.w); } } } void solve() { cin n m; for (int i 0; i m; i) { int x, y, z; cin x y z; mp[x].push_back({y, z}); // 无向图双向存边 mp[y].push_back({x, z}); } // 初始化距离数组为无穷大 for (int i 1; i n; i) d[i] inf; sum 0; prim(); if (sum inf) cout orz endl; else cout sum endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }堆优化版#include bits/stdc.h using namespace std; #define int long long const int N 2e6 10; const int inf 2147483647; // 无穷大 // 邻接表存储边u是终点w是边权 struct node { int u, w; }; // 堆节点存储【当前节点到生成树的最小距离】【节点编号】 struct HeapNode { int dis, id; // 小根堆重载让优先队列从小到大弹出距离越小越优先 bool operator(const HeapNode other) const { return dis other.dis; } }; bool st[N]; // 标记节点是否已经加入最小生成树 vectornode mp[N];// 邻接表存图 int d[N]; // d[i]节点i到已选生成树的最小边权 int n, m, sum; // n点数m边数sum生成树总权值 void prim() { // 1. 初始化所有节点到生成树的距离设为无穷大 for (int i 1; i n; i) d[i] inf; // 初始化所有节点未被访问 memset(st, 0, sizeof st); sum 0; // 总权值归零 d[1] 0; // 从 1 号节点开始初始距离为 0 // 小根堆每次取出【距离最小】的节点 priority_queueHeapNode q; q.push({0, 1}); // 将起点距离0编号1推入堆 int cnt 0; // 记录已经加入生成树的节点数量 // 2. 开始循环堆不为空就继续 while (!q.empty()) { // 取出堆顶当前距离最小的节点 auto now q.top(); q.pop(); int u now.id; // 当前节点编号 int dis now.dis;// 当前节点到生成树的最小距离 // 3. 重要剪枝如果这个节点已经加入过生成树直接跳过堆里的旧数据 if (st[u]) continue; // 4. 标记该节点已加入生成树 st[u] true; sum dis; // 累加这条边的权值 cnt; // 已加入节点数 1 // 5. 遍历当前节点的所有邻边松弛操作 for (auto edge : mp[u]) { int v edge.u; // 邻接点编号 int w edge.w; // 这条边的权值 // 6. 如果邻接点没被选过且新边权更小 → 更新距离 if (!st[v] d[v] w) { d[v] w; // 更新最小距离 q.push({d[v], v}); // 新状态推入堆 } } } // 7. 最终判断如果加入的节点数 ! 总点数 → 图不连通 if (cnt ! n) sum inf; } void solve() { cin n m; // 读入 m 条无向边存入邻接表 for (int i 0; i m; i) { int x, y, z; cin x y z; mp[x].push_back({y, z}); mp[y].push_back({x, z}); } // 执行堆优化 Prim prim(); // 输出答案不连通输出 orz否则输出总权值 if (sum inf) cout orz\n; else cout sum \n; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }4. 算法优缺点与Kruskal 算法一直都是在对边进行操作相对Prim一直在对点进行操作故而✅ 优点稠密图效率极高边多、节点少的图无需存储所有边❌ 缺点朴素版代码理解难度略高于 Kruskal时间复杂度朴素版O(n2)堆优化版O(mlogn)n 为节点数四、两大算法核心对比面试 / 做题必背维度Kruskal 算法Prim 算法核心思路边贪心从小到大选边点贪心扩张点集数据结构优先队列 / 排序 并查集邻接表 距离数组判环方式并查集判断连通块无需判环点集天然无环适用场景稀疏图边少m 远小于 n²稠密图边多m 接近 n²代码难度简单新手首选中等时间复杂度O(mlogm)朴素版O(n2)五、做题小技巧稀疏图无脑用 Kruskal代码短不易错稠密图用 Prim 朴素版效率拉满数据范围节点数≤1e4 用 Prim边数≤1e6 用 Kruskal六、总结最小生成树的本质就是贪心Kruskal选最小的边不环就留靠并查集实现Prim扩最小的点逐步连通靠距离数组实现。关键点回顾最小生成树连通所有节点、n-1 条边、总权最小、无环Kruskal边排序 并查集稀疏图首选O(mlogm)Prim点集扩张 距离数组稠密图首选O(n2)核心都是贪心根据图的疏密选择算法即可本篇文章主要介绍两个最小生成树算法里面有一些比如优先队列的重载并没有讲后续还会写专门介绍优先队列使用方法
