最小生成树

生成树 : 如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树

最小生成树 : 边权和最小的生成树叫做最小生成树。如果原图不连通，则没有最小生成树

求最小生成树有两种方法 ： prim 和 kurskal

一. prim算法

将最小生成树看做一个集合，每次选取距离集合最近的点，如果这个点不在集合中则加入集合，也就意味着这个点和集合里的点所连成的边加入了集合。最后等到所有点都加入集合则所有进入集合的边构成最小生成树。

例题1 prim板子

给你一张 n 个顶点 m 条边的无向简单连通图，顶点编号从 1 到 n，每条边都有一个边权，边权为非负整数。

请求出这张图的最小生成树，只需要输出最小生成树的边权和即可。

输入格式
第一行两个整数 n,m 表示图的顶点数、边数。

接下来 m 行，每行三个整数 x,y,z 表示 x 号点与 y 号点之间有一条边权为 z 的边。

数据保证图中顶点两两连通。

输出格式
输出一行一个数，表示最小生成树的边权和。

样例输入
4 4
1 2 1
2 3 3
3 4 1
1 4 2
样例输出
4
数据规模
对于所有数据，保证 2≤n≤1000,n−1≤m≤100000,1≤x,y≤n,1≤z≤10000

代码

# include<bits/stdc++.h>
 
using namespace std;
typedef pair<int,int> pii;
 
const int N = 1e4+10;
vector<pii> edge[N];
int dist[N];	//这里的dist是指点到集合（生成树）的距离
bool st[N];
int n,m;
 
int prime()
{
	memset(dist,0x3f,sizeof dist);
	dist[1] = 0;
	priority_queue<pii,vector<pii>,greater<pii> > q;
	q.push({dist[1],1});
	int ans = 0;			//ans是最小生成树的权值和
	int tot;tot = 0;		//tot存的是集合中的点的数量，如果结束的时候tot ！= n则证明无法构造出生成树
	while(q.size())
	{
		auto t = q.top();q.pop();	//找出距离集合最小的点
		if(st[t.second]) continue;	//每次取到集合最近的点，如果这个点已经在集合中则continue
		tot++;
		ans+=t.first;st[t.second] = true;
		for(auto i:edge[t.second])
		{
			if(dist[i.first]>i.second) 	//注意这里dist要和边权比，因为边权最终是距离集合的距离
			{
				dist[i.first] = i.second;
				q.push({dist[i.first],i.first});
			}
		}
	}
	if(tot!=n) return -1;
	return ans;
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		edge[x].push_back({y,z});edge[y].push_back({x,z});
	}
	cout<<prime()<<endl;
	return 0;
}

例题2

在一片海域上有 n

标签：dist,int,边权,最小,生成,edge
From： https://www.cnblogs.com/algoshimo/p/17566277.html