c++最小生成树两种方法：Prim算法 和 Kruskal算法

c++最小生成树两种方法： Prim算法 和 Kruskal算法

Prim算法： 算法思想： 假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作： 在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。 此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。 Prim算法的核心:始终保持TE中的边集构成一棵生成树。

算法过程： 随意选取一点 ， 寻找最小权值

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f,maxn=100,maxm=maxn*maxn;

struct edge{
          
   
	int from,to,w,nxt;
}e[maxm];

int n,m,head[maxn],cnt,dis[maxn],u,v,w,ans;
bool vis[maxn];

void add(int u,int v,int w){
          
   
	e[++cnt].from=u;
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}//链式前向星定义

int main(){
          
   
	cin>>n>>m;
	memset(head,-1,sizeof(head));
	memset(vis,0,sizeof(vis));//集体赋值
	for(int i=0;i<m;i++){
          
   
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);//无向图两次定义
	}
	memset(dis,inf,sizeof(dis));//未知点赋较大值
	dis[1]=0;//从dis[1]开始寻找
	for(int i=0;i<n;i++){
          
   
		int minw=inf,v;
		for(int x=1;x<=n;x++){
          
   
			if(!vis[x] && dis[x]<=minw){
          
   
				minw=dis[x];
				v=x;
			}
		}
		ans+=minw;
		vis[v]=true;//标点
		for(int k=head[v];k!=-1;k=e[k].nxt){
          
   
			if(e[k].w<dis[e[k].to] && !vis[e[k].to]){
          
   
				dis[e[k].to]=e[k].w;
			}
		}
	}
	cout<<ans;
	return 0;
}

//Prim算法

Kruskal算法： 算法思想： 权重最小生成树问题是指在一棵无向全连接图中找到一个无环子集T，既能将所有的结点连接起来，又具有最小的权重和。

解决问题的核心是每次找到一条安全边加入到边集合A中，使得A仍然是某棵最小生成树的子集。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define M 100000

int n,m,ans,fa[M];

struct edge{
          
   
	int u,v,w;
}e[M];

bool cmp(edge a,edge b){
          
   
	return a.w < b.w;
}

int getroot(int x){
          
   
	if(x!=fa[x]){
          
   
		fa[x]=getroot(fa[x]);
	}
	return fa[x];
}

int main(){
          
   
	cin>>n>>m;
	for(int i=1;i<=m;i++){
          
   
		cin>>e[i].u>>e[i].v>>e[i].w;
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=n;i++){
          
   
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
          
   
		int p=getroot(e[i].u),q=getroot(e[i].v);
		if(p != q){
          
   
			fa[p]=q;
			ans+=e[i].w;
		}
	}
	cout<<ans;
	return 0;
}

//Kruskal算法

戳下方链接 最小生成树模板题

小结： 最小生成树相较于最短路的dijkstra算法和SPFA算法有相似之处，也比最短路容易理解。但要学会这个算法，融会贯通，还需要多下功夫。