kruskal最小生成树算法0(mlogn)

	#include<iostream>
	#include<algorithm>
	#include<stdio.h>
	#include<cstring>
	using namespace std;
	const int N=600000;
	int fa[N],n,m,ans;
	struct rec{
	int x,y,z;
	}edge[N];
	bool operator<(rec a,rec b)
	{
	   return a.z<b.z;
	}
	int get(int x)//并查集找父亲
	{
	if(x==fa[x])return x;
	return fa[x]=get(fa[x]);
	}
	int main()
	{
	cin>>n>>m;
	for(int i=1;i<=n;i++)//并查集初始化
	 fa[i]=i;
	 int k=0;
	for(int i=1;i<=m;i++)
	 cin>>edge[i].x>>edge[i].y>>edge[i].z;
	sort(edge+1,edge+m+1);
	for(int i=1;i<=m;i++)
	{
	int x=get(edge[i].x);
	int y=get(edge[i].y);
	if(x==y)
	continue;
	else{
	    fa[x]=y;
	ans+=edge[i].z;
	k++;
	    }
	}
	    if(k<n-1)//不存在
	    printf("impossible");
	    else
	    printf("%d",ans);
	
	return 0;
	}

Prim 最小生成树算法

	#include<iostream>
	#include<algorithm>
	#include<stdio.h>
	#include<cstring>
	using namespace std;
	const int N=60010;
	int a[N][N],d[N],ans,n,m;
	bool v[N];
	void prime()
	{
	memset(d,0x3f,sizeof(d));
	memset(v,0,sizeof(v));
	d[1]=0;//这个是已1为起点
	for(int i=1;i<=n;i++)
	{
	int x=0; 
	for(int j=1;j<=n;j++)  //找到剩下的没选的里面的最小值的下标
	  if(!v[j]&&(x==0||d[j]<d[x])) x=j;
	 v[x]=1;//把他加到已经选的点中 
	for(int y=1;y<=n;y++)
	if(!v[y])d[y]=min(d[y],a[x][y]);//更新值
	}
	int main()
	{
	cin>>n>>m;
	memset(a,0x3f,sizeof(a));
	for(int i=1;i<=n;i++)a[i][i]=0;//自己到自己权值是0
	for(int i=1;i<=m;i++)
	{int x,y,z;
	cin>>x>>y>>z;
	a[x][y]=a[y][x]=min(a[x][y],z);
	}
	prim();
	for(int i=2;i<=n;i++)
	ans+=d[i];
	printf("%d",ans);
	}

最小生成树

原文：https://www.cnblogs.com/arbor-one/p/12747185.html