[贪心算法]最小生成树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[贪心算法]最小生成树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2534字，纯文字阅读大概需要4分钟。

内容图文

（带全无向连通）图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树。 

1.Prim算法

主要思想：

//6 10   1 2 6  1 3 1  1 4 5  2 3 5  2 5 3  3 4 5  3 5 6  3 6 4  4 6 2  5 6 6  
//9 14   1 2 4  1 8 8  2 3 8  2 8 11  3 4 7  3 6 4  3 9 2  4 5 9  4 6 14  5 6 10  6 7 2  7 8 1  7 9 6  8 9 7
#include<iostream>
using namespace std;
#define MAX_V 5005
#define MAX 0x7fffff
int verNum,edgeNum,sum=0;
int edge[MAX_V][MAX_V];
int pre[5005];//数组用于临时存储当前选中边的另一个端点，每次输出选中情况后更新为-1不在参与接下来的工作
void Prim()
{
	int *dist=new int[verNum+1];//数组从1开始，防RE
	for(int i=1;i<=verNum;i++)
	{
		dist[i]=edge[1][i];
		pre[i]=1;
	}
	pre[1]=-1;//以1作为源点
	for(int i=1;i<verNum;i++)
	{
		int temp=MAX;
		int x=0;
		for(int j=1;j<=verNum;j++)
		{
			if(pre[j]!=-1&&dist[j]<temp)//寻找未选中的距离最小的边
			{
				x=j;
				temp=dist[j];
			}
		}
		//cout<<pre[x]<<"->"<<x<<":"<<temp<<endl;
		pre[x]=-1;
		sum+=temp;
		for(int i=2;i<=verNum;i++)
		{
			if(pre[i]!=-1&&edge[x][i]<dist[i])
			{
				dist[i]=edge[x][i];//区分于单源最短路径，dist数组表示的是该点到当前最小生成树的边的距离，不是到源点的距离
				pre[i]=x;
			}
		}
	}
}
int main()
{
	cin>>verNum>>edgeNum;
	for(int i=1;i<=verNum;i++)
		for(int j=1;j<=i;j++)
			edge[i][j]=edge[j][i]=MAX;
	for(int i=1;i<=edgeNum;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		edge[b][a]=edge[a][b]=min(c,edge[a][b]);//洛谷防重边
	}
	Prim();
	bool flag=true;
	for(int i=1;i<=verNum;i++)
		if(pre[i]!=-1)
		{
			flag=false;
			break;
		}
	if(flag==true)
		cout<<sum<<endl;
	else
		cout<<"orz"<<endl;
	return 0;
}

2.Kruskal算法

主要思想：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
//6 10   1 2 6  1 3 1  1 4 5  2 3 5  2 5 3  3 4 5  3 5 6  3 6 4  4 6 2  5 6 6  
//9 14   1 2 4  1 8 8  2 3 8  2 8 11  3 4 7  3 6 4  3 9 2  4 5 9  4 6 14  5 6 10  6 7 2  7 8 1  7 9 6  8 9 7
int vertexnum,edgenum;//点的总数和边的总数
int root[105];//记录每个点的上级
struct Graphic
{
	int weight;
	int x;
	int y;
}g[100005];
bool cmp(Graphic a,Graphic b)
{
	return a.weight<b.weight;
}

int find(int x,int y)//查找x的根
{
	if(root[x]==x||root[y]==y)
		return 1;
	for(int i=0;i<vertexnum;i++)
	{
		if(root[x]==y)
		{
			return 0;//在同一集合内
		}
		else
			x=root[x];
	}
	return 1;
}
void kruskal()
{
	int i,j;
	for(int k=1;k<=edgenum;k++)
	{
		i=g[k].x;
		j=g[k].y;
		if(find(i,j))//如果没有在一个集合内
		{
			cout<<i<<" -> "<<j<<" : "<<g[k].weight<<endl;
			swap(root[i],root[j]);//交换双方的root，使他们在同一个集合中（一直对其中一个点的root做回溯（?）一定能找到对应的路径使两点相连
		}
	}
}
int main()
{
	cin>>vertexnum>>edgenum;
	for(int i=1;i<=vertexnum;i++)
		root[i]=i;
	for(int i=1;i<=edgenum;i++)
		cin>>g[i].x>>g[i].y>>g[i].weight;
	sort(g,g+edgenum+1,cmp);//按权重从小到大排序
	kruskal();
	return 0;
}

 

 

 

内容总结

以上是互联网集市为您收集整理的[贪心算法]最小生成树全部内容，希望文章能够帮你解决[贪心算法]最小生成树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---