最小生成树学习

最小生成树学习

小鱼干 109 2022-10-21

知识点

图与树:在无向图中,连通且不成环的图称为树(Tree)。

生成树:给定无向图G=(V,E),连接G中所有点,且边集是E的n-1条边构成的无向连通子图称为G的生成树(Spanning Tree),而边权值总和最小的生成树称为最小生成树(Minimal Spanning Tree,MST)。

常见两种算法:

  1. Kruskal
  2. Prim算法

定理

任意一棵最小生成树一定包含无向图中权值最小的边。

证明

​ 反证法:假设图G=(V,E)存在一棵最小生成树且不包含权值最小的边e=(x,y,z)。将最短边e加入这个生成树,那么必定能在树中形成一个环。e可替代该环中的任意一条边,使得环中的点依旧连通,整棵树依旧连通,仍属于生成树。已知e为最短边,那么被替换的边权值一定>z。替换后的生成树的权值和小于原来的生成树,与假设矛盾。故假设不成立,原命题成立。

​ 证毕。

推论

给出一张无向图G=(V,E),n=Vn=|V|,m=Em=|E| 。从E中选出k<n-1 条边构成G的一个生成森林。若再从剩余的m-k条边中选n-1-k条添加到生成森林中,使其成为G的生成树,并且选出的边的权值之和最小,则该生成树一定包含这m-k条边中连接生成森林的两个不连通节点的权值最小的边。

把森林视为一个大的节点,即可用之前的反证法证明其正确性。

Kruskal算法

利用推论,我们针对边进行处理。通过寻找两端点不连通的最短的边,使得两个端点所处的不连通的两个节点能够连通,合并成一个更大的节点,不断重复直到所有节点都连通为止。

第一步:给所有边按照从小到大的顺序排列。

第二步:从小到大依次考查每条边(u,v)

  1. u和v在同一个连通分量中,那么加入(u,v)后会形成环,因此不能选择。

  2. 如果u和v在不同的连通分量,那么加入(u,v)一定是最优的。

    反证法证明:
    如果不加这条边能得到一个最优解T,则T+(u,v)一定有且只有一个环,而且环中至少有一条边(u’,v’)的权值大于或等于(u,v)的权值。删除该边后,得到的新树T=T+(u,v)-(u’,v’)不会比T更差,因此,加入(u,v)不会比不加入差。

伪代码

sort(e+1,e+m+1);//对m条边e[i]按从小到大进行排序
初始化MST为空
初始化连通分量,让每个点自成一个独立的连通分量
for(int i=1;i<=m;i++){
    if(e[i].u)和e[i].v不在同一个连通分量){
        把边e[i]加入MST
        合并e[i].u和e[i].v所在的连通分量
    }
}

todo1:连通分量的查询与合并,需要查询任意两个点是否在同一个连通分量中,还需要合并两个连通分量。

使用并查集(Union-Find Set)完成这一步。

复习并查集:

把每个连通分量看作一个集合,该集合包含了连通分量中的所有点。在途中,每个点恰好属于同一个连通分量,对应到集合表示中,每个元素恰好属于一个集合。所有的连通分量可以用若干个不相交集合来表示。

查找

int find(int x){//寻找x所在树的根节点
    if(p[x]==x) return x;
    else return p[x]=find(p[x]);
    //reutrn p[x]==x?x:p[x]=find(p[x]);
}

算法步骤整理:

  1. 建立并查集,每个点各自构成一个集合。
  2. 把所有边按照权值从小到大排序,依次扫描每条边(x,y,z)。
  3. 若x,y属于同一个集合(连通),则忽略这条边,并把z累加到答案中。
  4. 否则,合并x,y所在的集合,并把z累加到答案中。
  5. 所有边扫描完成后,第4步中处理过的边就构成最小生成树。

时间复杂度:Θ(mlogm)\Theta(mlogm)

Kruskal实现代码

int Kruskal(){
    int ans=0;
    for(int i=1;i<=n;i++) p[i]=i;//初始化并查集
    sort(e+1,e+m+1,cmp);//对边按权值从小到大排序
    int cnt=0;
    for(int i=1;i<=m;i++){
        int u=e[i].u,v=e[i].v;
        int x=find(u),y=find(v);
        //找出两个端点所在集合的编号
        if(x!=y){
        	cnt++;
            ans+=e[i].w;//累加权值和
            p[x]=y;//合并两个端点
            if(cnt==n-1) break;
        }
    }
    return cnt<n-1?0:ans;//返回最小生成树的最大权值;不存在则返回0
}

Prim算法

依旧基于之前的推论。区别在于,Kruskal算法是通过对边的寻找连接两个非连通节点的最小权值的边;而prim则是通过对点的寻找去确定最小权值的边。

最初,prim算法仅确定1号节点属于最小生成树。维护数组dis,dis[x]的含义为节点x与MST集合的连通的最小边权值。

算法步骤整理:

  1. 将1号节点加入MST集合。
  2. 遍历所有非MST集合的节点,并寻找dis值最小的。
  3. 标记找出的最小的节点,并累加dis值。
  4. 扫描所有的出边,更新另一个端点的dis值。
  5. 重复2~4直到所有节点都加入MST。

时间复杂度:Θ(n2)\Theta(n^2)

prim主要用于稠密图,尤其是完全图的最小生成树求解。

int prim(){//prim最小生成树算法
	//返回最小生成树最大权值,不存在返回0
	int ans=0;//最大权值
	vis[1]=1;//将1加入MST集合
	memset(dis,0x3f,sizeof(dis));//初始化dis为极大值
	dis[1]=0;
	for(int i=0;i<(int)G[1].size();i++){
		int v=G[1][i].v,w=G[1][i].w;
		dis[v]=min(dis[v],w);//更新1的邻接点,注意重边
	}
	
	int cnt=1;//MST集合中的节点个数
	while(cnt<n){//循环,直到所有点连通
		int idx=-1;
		for(int i=1;i<=n;i++){//寻找与MST集合邻接的最近的点
			if(vis[i] || dis[i]==dis[0]) continue;//跳过已在MST集合中的和不邻接的点
			if(idx==-1||dis[i]<dis[idx]) idx=i;//更新最近点的下标
		}
		if(idx==-1) break;//未找到则结束循环
		cnt++;//更新MST集合个数
		vis[idx]=1;//标记
		ans=max(ans,dis[idx]);//更新最大权值
		//遍历idx 的邻接点
		for(int i=0;i<(int)G[idx].size();i++){
			int v=G[idx][i].v,w=G[idx][i].w;
			if(vis[v]) continue;
			if(dis[v]>w) dis[v]=w;//更新其它点到MST集合的距离
		}
	}
	
	return cnt==n?ans:0;//返回最小生成树的最大权值;不存在则返回0
}

题目练习

  • P3366 【模板】最小生成树
  • P1546 [USACO3.1] 最短网络 Agri-Net
  • P2820 局域网
  • P2330 [SCOI2005]繁忙的都市
  • UVa1395 Slim Span
  • Uva1151 Buy or Build