最小生成树

生成树 : 如果连通图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𝑛 个岛屿,第 ii 个岛屿的所在位置可以用二维坐标 (xi,yi) 表示,其中 xi𝑥𝑖, 都是整数。

我们想在这些岛屿之间修建桥梁,使得最终所有岛屿两两之间都可以通过桥梁到达。桥梁只能以岛屿作为起点和终点,桥梁的长度等于起点、终点两个岛屿的欧几里得距离。

由于经费有限,我们想花费最少的代价来修建桥梁(即建造的桥梁的长度和最小)。

请问建造的桥梁的长度和最小为多少?

输入格式
第一行一个整数 n。

接下来 n 行,每行两个整数 xi,yi,代表一个岛屿的坐标。

输出格式
输出一行一个数表示建造的桥梁的最小长度和,答案保留一位小数输出。

样例输入
3
0 0
4 4
0 4
样例输出
8.0
数据规模
对于所有数据,保证 2≤n≤800,0≤xi,yi≤1000两座岛屿不会出现在相同位置

我们可以先将每个点上连一条边,这样就可以建成一个n个点,n*(n-1)/2条边的无向图 然后再用prim求出这个图的最小生成树即可


代码

# include<bits/stdc++.h>
 
using namespace std;
 
typedef pair<int,double> pid;
typedef pair<double,int> pdi;
typedef pair<int,int> pii;
 
const int N = 810;
 
int n;
pii a[N]; 
vector<pid> edge[N];
bool st[N];
double dist[N];
 
double prim()
{
	for(int i=1;i<=n;i++) dist[i] = 1e9;
	dist[1] = 0;
	priority_queue<pdi,vector<pdi>,greater<pdi> > q;
	q.push({dist[1],1});
	double ans = 0;
	int tot = 0;
	while(q.size())
	{
		auto t = q.top();q.pop();
		if(st[t.second]) continue;
		st[t.second] = true;tot++;ans+=t.first; 
		for(auto i:edge[t.second]) 
		{
			if(dist[i.first]>i.second ) 
			{
				dist[i.first] = i.second;
				q.push({dist[i.first],i.first});
			}
		}
	}	
	return ans;		
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		a[i] = {x,y}; 
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			int x1 = a[i].first,y1 = a[i].second;
			int x2 = a[j].first,y2 = a[j].second;
			double w = sqrt ( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) );
			edge[i].push_back({j,w});
			edge[j].push_back({i,w});
		}
	}
	printf("%.1f",prim());
	return 0;
} 

二. kurskal算法

相较于prim的一个个往集合里添加点得到最小生成树,它是以一条条添加边的方式来求最小生成树

大致流程 :

1.初始化并查集,一开始所有点的代表元都是它自己,每个点本身构成一个集合

2.将所有边按照边权从小到大的顺序排序

3.按边权从小到大的顺序依次枚举所有边,如果当前这条边连接的每个顶点位于同一个集合则continue,否则将这条边添加到最小生成树的边集里并将两点所在集合合并

4.直到只剩下一个集合,算法结束

例题1 Kurskal板子

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

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

输入格式
第一行两个整数 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≤50000,n−1≤m≤100000,1≤x,y≤n,1≤z≤10000


代码

# include<bits/stdc++.h>
 
using namespace std;
 
const int N = 5e4+10;
const int M = 1e5+10;
 
struct Edge
{
	int u,v,w;
}edge[M];	//存每条边
 
int p[N];	//存每个元素的父节点
int n,m;
 
int find(int x) //找到x的祖先节点(并查集板子)
{
	if(p[x]!=x) p[x] = find(p[x]);	
	return p[x];
}
bool cmp(Edge x,Edge y)
{
	return x.w<y.w;
}
int kurskal()
{ 
	int ans = 0,tot = 0;				//ans是边权和,tot是加入集合的边的数量
	for(int i=0;i<m;i++)				//权值从小到大遍历每个边
	{
		int a = edge[i].u,b = edge[i].v;
		if(find(a) == find(b)) continue;	//如果一条边的两个端点在一个集合中,continue
		p[find(a)] = find(b);				//合并两个集合
		ans+=edge[i].w;	
		tot++;
	}
	if(tot<n-1) return -1;
	return ans;
}
 
int main()
{
	cin>>n>>m;
	for(int i=0;i<m;i++)	cin>>edge[i].u>>edge[i].v>>edge[i].w;
	sort(edge,edge+m,cmp);
	for(int i=1;i<=n;i++) p[i] = i;		//一开始把每个点的父节点都设为自己
	cout<<kurskal()<<endl;
	return 0;
}

例题2. 最小边权差生成树

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

请求出这张图的所有生成树中,边权最大的边的边权与边权最小的边的边权的差值最小是多少。

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

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

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

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

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

我们可以将所有边按边权从小到大排序,枚举每一条边是最小值的时候构成的生成树的最大边权差。一共做m次kurskal

代码

# include<bits/stdc++.h>
 
using namespace std;
typedef pair<int,int> pii;
 
const int N = 8010;
 
struct Edge
{
	int u,v,w;
}edge[N];
 
int n,m;
int p[N];
 
bool cmp(Edge x,Edge y)
{
	return x.w<y.w;
}
 
int find(int x)
{
	if(p[x] != x) p[x] = find(p[x]);
	return p[x];
}
 
int main()   
{
	cin>>n>>m;
	for(int i=0;i<m;i++)	cin>>edge[i].u>>edge[i].v>>edge[i].w;	
	sort(edge,edge+m,cmp);
	int ans = 0x3f3f3f3f;
	for(int i=0;i<m;i++)
	{
		for(int j=1;j<=n;j++) p[j] = j;
		int tot = 0;
		for(int j=i;j<m;j++)
		{
			
			int a = edge[j].u,b = edge[j].v;
			if(find(a) == find(b)) continue;
			p[find(a)] = find(b);
			tot++;   
			if(tot == n-1)	
			{
				ans = min(ans,edge[j].w - edge[i].w);
				break;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

热门相关:流鱼无恙   锦庭娇   闺范   戏精老公今天作死没   神算大小姐