最小生成树（Minimum Spanning Tree，MST）初步

定义

连通图的最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。

注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。

思路

分为 Kruskal 与Prim 两种算法。

Kruskal

从最小边权的边开始，按边权从小到大依次遍历。

若当前边连接的两点不连通，加入此边。

Prim

每次选择距离最小的结点，用节点所连接的边更新其他结点的距离。

可用堆优化，类似于 Dijkstra。

代码实现

Kruskal

#include <bits/stdc++.h>
using namespace std;
struct p{
int u, v, w;
}b[200005];
bool cmp(p x, p y){
	return x.w < y.w;
}
int n, m, F[5005];
int findf(int x){
	if(F[x] == x) return x;
	F[x] = findf(F[x]);
	return F[x];
}
int Kruskal(){
	sort(b + 1, b + m + 1, cmp);
	int mst = 0, cnt = 1;
	for(int i = 1; i <= m; i++){
	int x = findf(b[i].u), y = findf(b[i].v);
	if(x != y){
		cnt++;
		mst += b[i].w;
		F[x] = y;
		if(cnt == n)
			return mst;
	}
}
	return -1;
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++) F[i] = i;
	for(int i = 1; i <= m; i++) cin >> b[i].u >> b[i].v >> b[i].w;
	cout << Kruskal();
	return 0;
}

Prim

这里给出堆优化的 Prim

#include<bits/stdc++.h>
#define R register int//优化,可忽略
#define P pair <int,int>
using namespace std;
int k,n,m;
int cnt,sum,dis[10005],vis[10005];
vector <int> E[200005];//存点
vector <int> W[200005];//存边
inline void add(int u,int v,int w) {
	E[u].push_back(v);//存点
	W[u].push_back(w);//存边
}
priority_queue <P,vector<P>,greater<P> > q;//递减
inline void prim() {//神似dijskra
	memset(dis,127,sizeof(dis));//初始化
	dis[1]=0;//初始化
	q.push(make_pair(dis[1],1));//初始化
	while(!q.empty()&&cnt<n) {
		int d=q.top().first,u=q.top().second;
		q.pop();
		if(vis[u]) continue;//访问过就不访问了
		cnt++;
		sum+=d;//有就加
		vis[u]=1;
		for(R i=0; i<E[u].size(); i++)//dijskra这里是循环找中界点,而这里则直接找与该点相邻的边,刷新一遍距离
		   if(W[u][i]<dis[E[u][i]]){
			dis[E[u][i]]=W[u][i]；
               		q.push(make_pair(dis[E[u][i]],E[u][i]));
    		}
	}
}
int main() {
	scanf("%d%d",&n,&m);
	for(R i=1; i<=m; i++) {
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	prim();
	if (cnt==n)printf("%d",sum);
	else printf("-1");
}

Thank's for your reading!