最小生成树

介绍

之前讲过最短路，是求两点之间的最短路径。
最小生成树，是指有n条边，m个点（n>=m）,寻任意条边，连接每一个点，使边权之和最小；$保证有解$

分析

因为需要连接m个点,我们要做的就是找出n-1条边，无环，且能连接m个点，还保证边权和最小。

如何去做呢？
提供2个算法Prim和Kruskal

算法

Prim

主要思想

一开是分两个集合S和T
S表示已确定的最小生成树点，T表示未扩展的点，lowcost[i]表示i点S集合的最近距离。
循环n-1次
每次遍历其他所有节点
如果该点未在S集合中且距离S集合的距离最小，记录
加入S集合
更新T集合点到S集合的距离

完美图解

模板代码（无优化）

void Prim(int n){
    
	//初始化 
	s[1]=true;
	for(int i=1;i<=n;i++){
    
		if(i!=1){
    
			lowcost[i]=c[1][i];
			closest[i]=1;
			s[i]=false;
		} 
		else lowcost[i]=0;
	}
	//n-1条边的添加 
	for(int i=1;i<n;i++){
    
		int temp=inf;
		int t=1;
		//寻找离已添加最近的节点t 
		for(int j=1;j<=n;j++){
    
			if(!s[j]&&lowcost[j]<temp){
    
				temp=lowcost[j];
				t=j; 
			}
		}
		if(t==1)break;
		s[t]=true;
		//更新未添加节点 
		for(int j=1;j<=n;j++){
    
			if(!s[j]&&c[t][j]<lowcost[j]){
    
				lowcost[j]=c[t][j];
				closest[j]=t;

			}
		}
	}
} 

复杂度

暴力：O(n^2+m)

二叉堆：O((n+m)*log(n)

Fib 堆：O(n*log(n)+m)

Kruskal

主要思想

Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法的基本思想是从小到大按边权排序，判断不是在同一集合的加入边集合，是个贪心算法。
（ps:运用到了并查集：https://blog.csdn.net/weixin_42178241/article/details/126013714）

完美图解

模板代码（无优化）

//边集数组 
struct node {
    
	int u,v,w;
}e[maxn];
//排序优先级，边权从小到大 
bool cmp(node x,node y){
    
	return x.w<y.w;
} 
//初始化 
void init(int n){
    
	for(int i=1;i<=n;i++)fa[i]=i;
}
//合并 
int merge(int a,int b){
    
	int p=fa[a];
	int q=fa[b];
	if(p==q)return 0;
	//不是同一祖先，合并赋值 
	for(int i=1;i<=n;i++){
    
		if(fa[i]==q)fa[i]=p;
	}
	return 1;
}
//求最小生成树 
int Kruskal(int n){
    
	int ans=0;
	sort(e,e+m,cmp);
	for(int i=0;i<m;i++){
    
		if(merge(e[i].u,e[i].v)){
    
			ans+=e[i].w;
			n--;
			//共执行n-1次合并，n=1时算法结束 
			if(n==1)return ans;
		}
	}
	return 0;
}

复杂度

O(m*log(m))