最小生成树(Prim普利姆算法、Kruskal克鲁斯卡尔算法)

朴素版prim用于稠密图  堆优化版prim与Kruskal用于稀疏图 

堆优化版prim太麻烦 不用学 直接用克鲁斯卡尔算法代替 

普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。

意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（Vertex ），且其所有边的权值之和亦为最小。在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。

👉详细解析加保存路径版👈

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int n,m;
int g[N][N];//存放两条边之间的权值
int dist[N];//存放某一点到连通部分的距离
bool st[N];//节点是否被加入到生成树
 
int prim(){
	memset(dist ,0x3f,sizeof dist);//任意一点到集合的距离初始化为无穷大
	dist[1]=0;//去第一个点作为起点  如果存在 最后每个点都要连接 所以取哪个点都可以
	int res=0;//存放权值之和
	for(int i=0;i<n;i++){//每次循环选出一个数加入生成树
		int t=-1;
		for(int j=1;j<=n;j++){//把每个节点都判断一次
			if(!st[j]&&(t==-1||dist[t]>dist[j]))//如果不在树中且到树的距离最短  就选择该点
			t=j;
		}
		if(dist[t]==0x3f3f3f3f) return 0x3f3f3f3f;//如果存在孤立点 直接return
		res+=dist[t];//把选中的到树最短距离的边加入到结果中
		st[t]=true;
		//法一 直接从1开始 方便写
// 		for(int j=1;j<=n;j++){
// 			dist[j]=min(dist[j],g[t][j]);//更新生成树外的节点到生成树的距离
// 		}
//		法二 实际不需更新已经确定过的点
		for(int j=1;j<=n;j++){
			if(dist[j]>g[t][j]&&!st[j]){
				dist[j]=g[t][j];
			}
		}
	}
	return res;
}
 
int main(){
	scanf("%d%d",&n,&m);
	memset(g,0x3f,sizeof g);//任意两点间的距离初始为无穷大
	while(m--){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		g[a][b]=g[b][a]=min(g[a][b],c);//有重边 所以取最小
	}
	int t=prim();
	if(t==0x3f3f3f3f) puts("impossible");
	else printf("%d\n",t);
	return 0;
}

克鲁斯卡尔（Kruskal）算法从另一途径求网的最小生成树。其基本思想是：假设连通网G=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），概述图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点构成一个连通分量为止 

👉 详解来这里👈

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=200010;
int p[N];
int n,m;//n个点集合  m个边的集合
struct Edge{
	int a,b,w;
}edges[M];
bool cmp(const Edge &x,const Edge &y){//类型为结构体名 不是数组名
	return x.w<y.w;//结构体中利用权值从小到大排序
}
//并查集的模板
int find(int x){
	if(p[x]!=x) p[x]=find(p[x]);
	return p[x];
}
int kruskal(){
	sort(edges,edges+m,cmp);
	for(int i=1;i<=n;i++) p[i]=i;
	int res=0,cnt=0;//res用于存最终结果 cnt用于存加入了多少条边
	for(int i=0;i<m;i++){
		int a=edges[i].a,b=edges[i].b,w=edges[i].w;
		if(find(a)!=find(b)){//a、b不在一个集合中  连接a到b                                                           
                  //如果在一个集合中 说明两点已经用另一种方式连接  继续连接a到b会形成环
			p[find(b)]=find(a);//让b的根节点的父节点等于a的根节点
			cnt++;
			res+=w;
		}
	}
	if(cnt<n-1) return 0x3f3f3f3f;
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int a,b,w;
		scanf("%d%d%d",&a,&b,&w);
		edges[i]={a,b,w};//把值存入结构体
	}
	int t=kruskal();
	if(t==0x3f3f3f3f) puts("impossible");
	else printf("%d\n",t);
	return 0;
}