图论之cruskal算法克鲁斯卡尔
目录
图论之cruskal算法（克鲁斯卡尔）
我们已经学了prim算法了，接下来我们来学一下cruskal算法，和prim算法不同的点就在于prim是不断的加结点，而cruskal是不断的加边，不断的加最小的边，我们需要把每个边的权值用结构体存起来，然后排序，从小到大遍历边，不断的加边
如图，我们从权值最小的边开始
当我们把1，2权值为2的边加上去的话，就不符合我们要找生成树的性质了，
那我们怎么维护生成树呢？我们可以把形成生成树的这些结点都放在一个集合里，然后接下来看插入的边的两个结点是不是位于生成树集合里，如果位于生成树集合的话就不连了
OK，那么废话不多说，我们来实现一下代码吧
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
struct node {
int x;//结点1
int y;//结点2
int z;//权值
}a[N];
int fa[N];
int find(int x)
{
if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void un(int x, int y)
{
int px = find(x); int py = find(y);
fa[px] = py;
}
bool cmp(const node& x, const node& y)
{
return x.z < y.z;
}
int ret = 0;
int cnt = 0;//记录加入了几条边
int kk()
{
sort(a + 1, a + 1 + m, cmp);
for (int i = 1; i <= m; i++)
{
int x1 = a[i].x, y1 = a[i].y;
int z1 = a[i].z;
int fx = find(x1), fy = find(y1);
if (fx != fy)
{
ret += z1;
cnt++;
un(fx, fy);
}
}
return cnt == n - 1 ? ret : INF;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
fa[i] = i;
}
for (int i = 1; i <= m; i++)
{
cin >> a[i].x >> a[i].y >> a[i].z;
}
int r = kk();
if (r == INF) cout << "orz" << endl;
else cout << r << endl;
return 0;
}