生成树算法

生成树

• 最小生成树
• • 一、prim算法
  • 二、Kruskal 算法
• 最大生成树
• 次小生成树

约定：下文的代码中，m为边的个数，n为点的个数

最小生成树

我们定义无向连通图的 最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。

注意：只有连通图才有生成树，而对于非连通图，只存在生成森林（好多生成树！）。

图的形式不唯一，但是保证边权和最小！！

一、prim算法

基于邻接矩阵的算法，对于密集图更为方便，且复杂度达到O(N*N),且受到邻接矩阵特性的时间空间限制

记录当前在树上的所有点，并维护该树（联通块）对外界的所有边的权值

dist [ x ]

增边：每次选取最小的

dist

加入该联通块

维护的过程是：每加入一个点，遍历它的所有（当前联通块外）出边，取这条出边的边权和

dist

的最小值更新

dist

数组

int prim(){
	
	memset(dist, 0X3f , sizeof dist);     初始化距离均为最大值
	int ans=0; 
	dist[1]=0;                             首点到自己距离为0 
	for(int i=1;i<=n;i++)
	{
		int tt=-1;                         初始化没有选中的点
		
		for(int j=1;j<=n;j++)              枚举所有的单点
		{
			if(!vis[j]&&(tt==-1||dist[tt]>dist[j]))tt=j;    取距离最小的单点（可以用优堆优化了！）
		}	
		
		vis[tt]=true;
		ans+=dist[tt];
		
		for(int i=1;i<=n;i++)dist[i]=min(dist[i],g[tt][i]);
	}
	return ans;
} 

           

注意事项：

• 最大值不能初始化过大：如果是int类型:

  0X7f

  到

  0X3f

  即可，过大可能会溢出
• 最后的修改时可以只修改没有访问过的节点的加一句判断

  if(!vis[i] )

• 典例：AcWing 1140. 最短网络

二、Kruskal 算法

以三元组（出边，入边，边权）的形式存边，便于后期对边进行排序

排序后，从小到大枚举每一条边，判断他的两条边是不是统一集合（同一联通块）

判断集合相同性的代码基于并查集！

分情况：

1，如果是，跳过

2，不是，集合合并，把边加进来

int kruskal()
{
	int ans=0;
	for(int i=1;i<=m;i++)
	{
		int f=a[i].f;
		int w=a[i].w;
		int t=a[i].t;
		
		int a=getfa(f);
		int b=getfa(t);
		if(a!=b)fa[a]=b,ans+=w;
	}
	return ans;
}
           

几点注意：

1，变量的命名一定要注意避免重名

2，并查集集合合并的操作合并的是根节点，修改的对象也是根节点的父亲

• 典例：AcWing 1141. 局域网

最大生成树

最大生成树算法和最小并无区别，只需把cmp函数的

<

改成

>

即可

特性：加入的边数限制

k

，在kruskal算法中加入边数的计数器

op

若是等于

k

即刻跳出并输出答案

注意：最大spanning tree不一定联通所有点

• 典例：洛谷 P2121 拆地毯
• 典例解答： AC代码

次小生成树