最小生成树

一、概念

生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。

最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

二、不带权最小生成树

设图中有N个点，每条边的权值为1：

我们每连接两个点都需要一条边，则连接N个点需要N-1条边，那么无权图的最小生成树的权值始终为N-1

三、带权最小生成树——Kruskal

#include <bits/stdc++.h>
using namespace std;
int n, m;
const int maxn = 1e3 + 10;
struct Node {
	int now, to, val;
}node[maxn];
int fa[maxn];
int cmp(Node a, Node b) {
	return a.val < b.val;
}
int findfa(int x) {
	if(fa[x] == x) return x;
	else {
		fa[x] = findfa(fa[x]);
		return fa[x];
	}
}
int main() {
	cin >> n >> m;
	int num = n, ans = 0;
	for(int i = 1; i <= m; i++) 
		cin >> node[i].now >> node[i].to >> node[i].val;
	for(int i = 1; i <= n; i++) fa[i] = i;
	sort(node + 1, node + m + 1, cmp);
	for(int i = 1; i <= m; i++) {
		int r1 = findfa(node[i].now);
		int r2 = findfa(node[i].to);
		if(r1 != r2) {  
			fa[r1] = r2;
			num--;
			ans += node[i].val;
		}
	}
	if(num > 1) cout << "无最小生成树";
	else cout << ans << endl;
	return 0;
}

四、带权最小生成树——Prim

1.清空生成树，任取一个顶点加入生成树

2.在那些一个端点在生成树里，另一个端点不在生成树里的边中，选取一条权最小的边，将它和另一个端点加进生成树

3.重复步骤2，直到所有的顶点都进入了生成树为止，此时的生成树就是最小生成树

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int vis[maxn], a[maxn][maxn];
int dis[maxn];//dis表示点i与当前生成树中的点有连边的边长的最小值 
int n, m, ans = 0;
const int inf = 0x7fffffff;
void prim(int x) {
	int k;
	for(int i = 1; i <= n; i++) dis[i] = inf;
	dis[x] = 0;
	for(int i = 1; i <= n; i++) {//遍历n个点
		int minn = inf;
		for(int j = 1; j <= n; j++)
			if(vis[j] == 0 && minn > dis[j]) {
				minn = dis[j];
				k = j;
			}
		vis[k] = 1;
		ans += dis[k];
		for(int j = 1; j <= n; j++)
			if(vis[j] == 0 && dis[j] > a[k][j]) dis[j] = a[k][j];  
		//更新dis数组:把与k点相连的所有点的最短边长更新为k到这个点的距离 
	}
} 
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) 
		for(int j = 1; j <= n; j++) a[i][j] = inf;//初始化
	for(int i = 1; i <= m; i++) {
		int x, y, z; cin >> x >> y >> z;
		a[x][y] = a[y][x] = z;
	}
	prim(1);
	cout << ans <<endl;
	return 0;
}