Kruskal算法求最小生成树

 

输入样例：

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

输出样例：

6

适用于稀疏图，快；

实现步骤：

1.将所有边将权重从小到大排序；sort；O（mlogm）

2.枚举每条边a,b；权重是c，如果ab不连通，加入到集合中去；O(m);

类似于并查集；

#include
using namespace std;
const int N = 1e6;
int n, m,p[N];
struct Edge {
	int a;
	int b;
	int w;
}edge[N];
 
bool cmp(Edge a, Edge b) {
	return a.w < b.w;
}
 
int find(int x) {
	if (p[x] != x) p[x] = find(p[x]);//p数组存的是x的祖先；
	return p[x];
 
}
 
void kruskal() {
	for (int i = 0;i < n;i++) p[i] = i;//初始化并查集
	sort(edge, edge + m, cmp);
 
	int res = 0;
	int cnt = 0;
	for (int i = 0;i < m;i++) {
		int a = edge[i].a, b = edge[i].b, w = edge[i].w;
		if (find(a) != find(b)) {
			p[find(a)] = p[find(b)];//将a,b所在的两个集合连接起来,即a，b祖先一样；
			cnt++;//因为加入的是a-b的这一条边,将a,b所在的两个集合连接之后,全部集合中的边数加1
			res += w;
		}
	}
 
	if (cnt == n - 1) {//树中有n个节点便有n-1条边,如果cnt不等于n-1的话,说明无法生成有n个节点的树
		cout << res << endl;
	}
	else cout << "impossible" << endl;
}
 
int main() {
	cin >> n >> m;
	for (int i = 0;i < m;i++) {
		int a, b, c;
		cin >> a >> b >> c;
		edge[i] = { a,b,c};
	}
	kruskal();
	
	return 0;
}