【算法】Kruskal最小生成树算法

目录

一、最小生成树

二、Kruskal算法求最小生成树

三、代码

---

一、最小生成树

什么是最小生成树？ 

对于一个n个节点的带权图，从中选出n-1条边（保持每个节点的联通）构成一棵树（不能带环），使得所有边的权值和最小，即为最小生成树

要点：

• 选n-1条边
• 要构成一颗树，则树中不能带环
• 节点间要互相连通，即从一个节点能够到达任意一个节点
• 边的权重和最小

---

二、Kruskal算法求最小生成树

Kruskal算法适用于稀疏图，因为其过程基于边的选择，如果图中的边过多可能导致效率变低

其思路如下：

• 将图中的所有边去掉，只留下节点
• 按照边权的顺序，从权重小的边开始将边回填到图中
• 如果某个边回填到图中会导致带环，则丢弃
• 当回填了n-1条边，得到最小生成树

例如：

这是我们的原图

去掉所有的边

按照权重从小到大回填边

此时发现有两条权重为4的边，选择哪条都可以，这也说明我们的最小生成树并不是唯一的，但最小权重和一定是唯一的

此时有两条权重为5的边，但如果我们把V1和V4之间的边回填的话，就带环了，这是不符合要求的，因此我们选择V2和V3之间的边

此时已经选择了n-1条边，我们的最小生成树就为

---

三、代码

Kruskal算法的思想很容易理解，但代码实现还是有些难度的

例如我们该如何判断图中是否带环呢？其实很简单，如果在回填某条边时，边两端的节点位于同一个集合中就说明带环。我们可以使用并查集来判断

关于并查集，可以阅读：

【算法】并查集-CSDN博客https://blog.csdn.net/Eristic0618/article/details/138584962接下来写一道例题练练手

P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug(x) cout << #x << " = " << x << '\n'
#define INF 0x3f3f3f3f
using namespace std;#define N 5050
#define M 200020int n, m;
int f[N]; //并查集 struct edge
{int a, b, w;
}e[M];int cmp(struct edge a, struct edge b)
{return a.w < b.w;
}int check(int num) //查询某个节点所在集合的根 
{if(f[num] != num) return f[num] = check(f[num]); //压缩路径：将路径上每个节点的父亲都修改为根节点 return num;
}void merge(int a, int b) //合并两个节点所在集合
{if(a == b) //a,b相同 return;f[a] = b; //a的父节点置为b 
} bool same(int a, int b) //判断两个节点是否在同一集合 
{if(f[a] == f[b]) return true; //a,b父节点相同，说明在同一集合 else return false;
}int Kruskal()
{for(int i = 1; i <= n; i++) //初始化并查集 {f[i] = i;}sort(e, e+m, cmp); //按照边权升序排序 int cnt = 0; //统计当前选择了多少条边 int ans = 0; //最小生成树边权和 for(int i = 0;i < m; i++) //遍历所有边 {int a = e[i].a, b = e[i].b, w = e[i].w;a = check(a), b = check(b);if(same(a, b)) //a与b处于同一连通分量continue;//a与b不处于同一连通分量ans += w; //选择该条边merge(a, b); //将a，b所在连通分量合并 cnt++;if(cnt == n-1) //已选择n-1条边 break;} if(cnt < n-1) //边数不足return -1;return ans; 
}void solve()
{cin >> n >> m;for(int i = 0;i < m; i++){int x, y, z;cin >> x >> y >> z;e[i] = {x, y, z}; //存边 }int ans = Kruskal(); //Kruskal算法if(ans == -1) //不连通 cout << "orz" << endl;elsecout << ans << endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;//cin >> t;while(t--)solve();return 0;
}

完.