kruskal求最小生成树

算法思路：

将所有边按照权值的大小进行升序排序，然后从小到大一一判断。

如果这个边与之前选择的所有边不会组成回路，就选择这条边分；反之，舍去。

直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。

筛选出来的边和所有的顶点构成此连通网的最小生成树。

判断是否会产生回路的方法为：使用并查集。

在初始状态下给各个个顶点在不同的集合中。

遍历过程的每条边，判断这两个顶点的是否在一个集合中。

如果边上的这两个顶点在一个集合中，说明两个顶点已经连通，这条边不要。如果不在一个集合中，则要这条边。

 

//kruskal求最小生成树
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 9;struct Edge
{int a, b, w;bool operator< (const Edge& W) const{return w < W.w;}
} edges[N];int n, m, p[N], res, cnt;int find(int x)
{if (p[x] != x) p[x] = find(p[x]);return p[x];
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 0; i < m; ++i){int a, b, w; cin >> a >> b >> w;edges[i] = { a, b, w };}//从小到大排序sort(edges, edges + m);//并查集数组初始化for (int i = 1; i <= n; ++i) p[i] = i;//如果这个边与之前选择的所有边不会组成回路，就选择这条边分；反之，舍去。//判断是否会产生回路的方法为：使用并查集。//每次将未加入的边加入到集合中去for (int i = 0; i < m; ++i){int a = edges[i].a, b = edges[i].b, w = edges[i].w;//不在一个集合里面a = find(a), b = find(b);if (a != b){res += w;cnt++;p[a] = b;//加入集合}}//如果集合中的边数小于n - 1，说明不存在最小生成树if (cnt < n - 1) cout << "impossible";else cout << res;return 0;
}

关于并查集可以看一下我写的这个篇文章： http://t.csdnimg.cn/ClmtA