图论：最小生成树

今天要介绍两中最小生成树的算法，分别是prim算法和kruskal算法。

最小生成树是所有节点的最小连通子图，即：以最小的成本（边的权值）将图中所有节点链接到一起。

图中有n个节点，那么一定可以用n-1条边将所有节点连接到一起。

那么如何选择这n-1条边就是最小生成树算法的任务所在。

prim算法：

prim算法是从节点的角度采用贪心的策略每次寻找距离最小生成树最近的节点并加入到最小生成树中。prim算法核心就是以下三步：

1. 第一步，选距离生成树最近非生成树节点
2. 第二步，最近节点加入生成树
3. 第三步，更新非生成树节点到生成树的距离（即更新ans数组）

ans数组用来记录每一个节点距离最小生成树的最近距离 

这样我们只需要遍历n-1此就能将所有的n-1条最优边给找出来！每次循环都是以上三个步骤，每次的步骤三都能选出一条最优的边，因为步骤一是从ans数组中找的，是目前所有的可达点中代价最小的选择，然后以当前的选择为起点开始遍历剩余的新的可达点以及更新其他可达点的距离最小生成树最近的距离，贪心体现在所有的与最小生成树相连的节点中找出一个代价最小的，不断的以当前最优解去遍历它的可达的节点。 

prim模板（邻接矩阵 + 遍历）

最小生成树prim算法的模板：ICPCer可拿 ！

#include using namespace std;#define endl \'\\n\'#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)const int inf = 0x3f3f3f3f; // 代替MAX，标准无穷大表示void solve() { int n, m; cin >> n >> m; vector<vector> e(n + 1, vector(n + 1, inf)); // 邻接矩阵，初始为inf vector v(n + 1, false); // 是否在MST中 vector ans(n + 1, inf); // 存储各点到MST的最小距离 // 建图，处理重边 for (int i = 1; i > u >> v >> x; e[u][v] = e[v][u] = min(e[u][v], x); // 无向图，取最小边 } ans[1] = 0; // 从节点1开始构建MST（可任选起点） int res = 0; // 最小生成树权值和 for (int i = 1; i <= n; i++) { // 循环n次，每次加入一个节点 int mi = inf, index = -1; // 1. 选取未访问的、距离MST最近的节点 for (int j = 1; j <= n; j++) { if (!v[j] && ans[j] < mi) { mi = ans[j]; index = j; } } if (index == -1) { // 图不连通 cout << \"No MST\" << endl; return; } v[index] = true; // 2. 加入MST res += mi; // 3. 更新未访问节点到MST的距离 for (int j = 1; j <= n; j++) { if (!v[j] && e[index][j] < ans[j]) { ans[j] = e[index][j]; } } } cout << res <> T; while (T--) solve(); return 0;}

prim模板（邻接表 + 优先队列） 

#include using namespace std;#define endl \'\\n\'#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)#define pii pairconst int inf = 0x3f3f3f3f; // 标准无穷大void solve() { int n, m; cin >> n >> m; vector<vector> e(n + 1); // 邻接表：e[u] = {v, w} vector vis(n + 1, false); // 是否在MST中 vector dis(n + 1, inf); // 存储各点到MST的最小距离 priority_queue<pii, vector, greater> pq; // 小根堆：{w, u} // 建图（无向图） for (int i = 1; i > u >> v >> w; e[u].push_back({v, w}); e[v].push_back({u, w}); } // 从节点1开始（可任选起点） dis[1] = 0; pq.push({0, 1}); int res = 0, cnt = 0; // res: MST权值和，cnt: 已加入节点数 while (!pq.empty() && cnt < n) { auto [w, u] = pq.top(); pq.pop(); if (vis[u]) continue; // 跳过已访问节点 vis[u] = true; // 加入MST res += w; cnt++; // 更新邻接节点到MST的距离 for (auto [v, w] : e[u]) { if (!vis[v] && w < dis[v]) { dis[v] = w; pq.push({w, v}); } } } cout << (cnt == n ? res : -1) <> T; while (T--) solve(); return 0;}

下面来看一道经典的最小生成树的模版题：（纯模板 因为用以上两个模板均可通过）

寻宝

题目链接：寻宝

这就是最小生成树的prim算法的模版题了，题目要求这几条路径中能够将所有点连接到一起的最短路径之和，也就是能够联通所有节点的最小代价，这时候就可以利用prim这一算法：

首先将所有的节点之间的代价用邻接矩阵存起来，因为是稠密图（点少边多所以用邻接矩阵），然后以节点1为最小生成树的根（以哪个都可以，1复合正常的逻辑而已），开始三部曲，第一二步就是选出了1作为起点，第三步就是遍历了所有与1相连的点，然后更新距离，此时来到了第二次循环还是到了第一步，在这几个点中找出距离最小生成树最近的节点并将其加入到最小生成树中（因为必须按照题目中所给的路径来，在前面的循环中就已经将目前能走的所有的路径以及可达点都走过了）所以要在这几个可达点中选出一条代价最小的路径，以此类推即可。注意这道题会卡内存，需要在输入n和m之后动态分配数组大小！

代码如下：

#include using namespace std;// #define int long long #define endl \'\\n\'#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);#define pii pair#define fi first#define se secondconst int N = 1e4+10;const int MAX = 10001;int n,m;void pre_handle(){} void solve(){cin>>n>>m;vector<vector> e(n+1,vector(n+1,MAX));//邻接矩阵：点少边多的情况更实用vector v(n+1,false);//是否在最小生成树中vector ans(n+1,MAX);//用于存放每个点到最小生成树的最短距离（最小代价） for(int i=1;i>u>>v>>x; e[u][v] = x; e[v][u] = x; } int res=0; for(int i=2;i<=n;i++)//循环n-1次即可 { int mi = MAX; int index = 1; // 1、prim三部曲，第一步：选距离生成树最近节点 for(int j=1;j<=n;j++)//找非生成树中距离最小生成树中的最小距离 { // 选取最小生成树节点的条件： // （1）不在最小生成树里 // （2）距离最小生成树最近的节点 if(!v[j] && ans[j] < mi) { //在所有的与最小生成树相连的节点中找出一个代价最小的 mi = ans[j]; index = j; } } // 2、prim三部曲，第二步：最近节点（index）加入生成树 v[index] = true;//加入到最小生成树中 // 3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新ans数组） // indx节点加入之后， 最小生成树加入了新的节点，那么所有节点到 最小生成树的距离（即ans数组）需要更新一下 // 由于index节点是新加入到最小生成树，那么只需要关心与 index 相连的 非生成树节点 的距离 是否比 原来 非生成树节点到生成树节点的距离更小了呢 for(int j=1;j<=n;j++) { if(!v[j] && e[index][j] < ans[j]) ans[j] = e[index][j]; } } for(int i=2;i<=n;i++) res += ans[i]; cout<<res<>T;while(T--) solve(); return 0;} 

注意最后从2到n累加  因为遍历了n-1此只需要统计n-1条边即可，1是起点，ans[1]还是初始最大值 

根据题目数据范围选择即可，建议两者均保存为模板备用。

 kruskal算法

kruskal算法和prim算法解决的是同一个问题，两者区别在于prim算法是以点构建最小生成树的，而kruskal算法则是通过边和边构成最小生成树的，详细区别如下：

个人感觉kruskal算法还是比prim好理解一点的，只需要将最小生成树抽象为一个集合然后用并查集对两个节点是否在最小生成树中进行查询即可！是不是很容易理解呢？对并查集不熟悉的小伙伴可以看主播的上一篇博客哟~

寻宝的kruskal解法

#include using namespace std;#define int long long #define endl \'\\n\'#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);#define pii pair#define fi first#define se secondconst int inf = 0x3f3f3f3f;const int N = 1e4 + 10;int n,m;vector tree(N);//并查集数组void init()//初始化并查集数组{ for(int i=1;i<=n;i++) tree[i] = i;}int find(int x)//并查集查找函数{ if(x == tree[x]) return x; return tree[x] = find(tree[x]);}void join(int x,int y){ x = find(x); y = find(y); if(x == y) return ; tree[x] = y; }bool is(int x,int y){ x = find(x); y = find(y); return x==y ? true : false;}struct edge{ int u,v,x;};vector e;bool cmp(const edge& x, const edge& y)//提升排序效率！{ return x.x >n>>m; init(); for(int i=1;i>u>>v>>x; e.push_back({u,v,x}); } sort(e.begin(),e.end(),cmp);//对边权进行排序 int res=0; for(auto i : e) { if(!is(i.u,i.v)) { join(i.u,i.v); res += i.x; } else continue;//可加可不加 } cout<<res<>T;while(T--) solve(); return 0;} 

kruscal的思路：

• 边的权值排序，因为要优先选最小的边加入到生成树里
• 遍历排序后的边
  • 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
  • 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合

kruskal模板 

最小生成树kruskal算法的模板：ICPCer可拿 ！

#include using namespace std;#define int long long // 使用long long类型#define endl \'\\n\' // 换行符#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) // 加速输入输出#define pii pair // 简写pair类型#define fi first  // 简写pair的first#define se second // 简写pair的secondconst int inf = 0x3f3f3f3f; // 定义无穷大const int N = 1e5+10; // 最大节点数，根据题目调整int n,m;  // n:节点数 m:边数vector tree(N); // 并查集数组// 初始化并查集void init(){ for(int i=1;i<=n;i++) tree[i]=i; // 每个节点初始父节点是自己}// 查找根节点（带路径压缩）int find(int x){ if(x == tree[x]) return x; // 找到根节点 return tree[x] = find(tree[x]); // 路径压缩}// 合并两个集合void join(int x,int y){ x = find(x); // 找到x的根 y = find(y); // 找到y的根 if(x == y) return; // 已经在同一集合 tree[x] = y; // 合并集合}// 判断两个节点是否在同一集合bool isSame(int x, int y){ return find(x) == find(y);}// 边结构体struct edge{ int u, v, w; // u:起点 v:终点 w:边权};vector e; // 存储所有边// 边权比较函数（用于排序）bool cmp(const edge& x, const edge& y){ return x.w >n>>m; // 输入节点数和边数 init(); // 初始化并查集 e.clear(); // 清空边集（多组数据时很重要） // 输入所有边 for(int i=1;i>u>>v>>w; e.push_back({u,v,w}); // 存储边 } sort(e.begin(),e.end(),cmp); // 按边权排序 int res=0,cnt=0; // res:最小生成树权值和 cnt:已选边数 for(auto& i : e) { if(!isSame(i.u,i.v)) // 如果边的两个端点不在同一集合 { join(i.u,i.v); // 合并集合 res += i.w; // 累加边权 cnt++; // 边数增加 if(cnt == n-1) break; // 已选够n-1条边，提前退出 } } // 输出结果（如果不能形成生成树输出-1） cout<<(cnt == n-1 ? res : -1)<> T; // 多组数据时取消注释 while(T--) solve(); return 0;}

 总结

此时我们已经讲完了 Kruskal 和 prim 两个解法来求最小生成树。

什么情况用哪个算法更合适呢。

Kruskal 与 prim 的关键区别在于，prim维护的是节点的集合，而 Kruskal 维护的是边的集合。 如果 一个图中，节点多，但边相对较少，那么使用Kruskal 更优。

为什么边少的话，使用 Kruskal 更优呢？

因为 Kruskal 是对边进行排序的后 进行操作是否加入到最小生成树。

边如果少，那么遍历操作的次数就少。

在节点数量固定的情况下，图中的边越少，Kruskal 需要遍历的边也就越少。

而 prim 算法是对节点进行操作的，节点数量越少，prim算法效率就越优。

所以在 稀疏图中，用Kruskal更优。 在稠密图中，用prim算法更优。

边数量较少为稀疏图，接近或等于完全图（所有节点皆相连）为稠密图

Prim 算法 时间复杂度为 O(n^2)，其中 n 为节点数量，它的运行效率和图中边树无关，适用稠密图。

Kruskal算法 时间复杂度 为 nlogn，其中n 为边的数量，适用稀疏图。