最小生成树学习

知识点

图与树：在无向图中，连通且不成环的图称为树（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=∣V∣n=|V|n=∣V∣,m=∣E∣m=|E|m=∣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)Θ(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)Θ(n2)

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

Q.E.D.