【算法笔记】最小生成树

前言

这个东西是老早就该补的坑了……

所以现在有时间了。

回来写一写。

最小生成树

定义：

简单来说，最小生成树是一张带权无向图里面由全部 \(n\) 个顶点，和边集中的 \(n-1\) 条边构成的原图的一颗生成树，且所有边权之和是所有生成树中最小的（可能有多个情况）。

而且它一定包含原图中最小的边。

推论：

设一张无向图 \(G=(V,E)\) ，从 \(E\) 中选出 \(k<|V|-1\)条边构成 \(G\) 的一个生成森林，然后再从剩余的 \(|E|-k\) 条边中选出 \(|V|-1-k\) 条边加入森林中，让它成为 \(G\) 的生成树，并且选出的\(\sum w\)最小。

那么，这个生成树一定包含 \(|E|-k\) 条边里面连接生成森林的两个不连通节点的权值最小的边。

很拗口对吧？

不过请好好理解，因为这个推论就是接下来的 \(\text{Kruskal}\) 的基础了。

Kruskal

这是一种求最小生成树的高效算法。

它维护图的最小生成森林。

开始的时候生成森林是空的，每一个节点就是一颗独立的树。

然后我们用上述推论维护森林就好了。

首先先搞一个并查集出来。对于每一个点初始化。

接下来按照边权升序排个序。

然后扫一遍每个边。

如果这一条边所连得两条边\((u,v)\)已经联通了。那么继续。

but，如果没有联通，根据这一条：

这个生成树一定包含 \(|E|-k\) 条边里面连接生成森林的两个不连通节点的权值最小的边。

所以满足了条件，那么我们就把这一条边加入到最小生成树里。

顺便合并一下 \((u,v)\) （相当于让它联通）

代码：

#include
using namespace std;

const int si=2e6+2;

int n,m;
int ans;
int pa[si];

struct edge{
    int x,y,val;
    bool operator < (const edge &u)const{
        return val>n>>m;
    for(register int i=1;i<=m;++i){
        cin>>ed[i].x>>ed[i].y>>ed[i].val;
    }
    sort(ed+1,ed+m+1);
    for(register int i=1;i<=n;++i){
        pa[i]=i;
    }
    for(register int i=1;i<=m;++i){
        if(Union(ed[i].x,ed[i].y)) ans+=ed[i].val;
    }
    cout<

Prim

这个算法实际上不是很常用。

因为在没有堆优化的情况下，\(\text{Prim}\) 的复杂度是 \(\text{O} (n^2)\)
的。

而且写了堆优化以后会比 \(\text{Kruskal}\) 麻烦的多（某次十一集训的时候xzq就是想写 \(\text{Prim}\) ，结果我用 \(\text{Kruskal}\) A了几道题了他还没调好/xyx）

那么大概说一下思路。

现在已经知道 \(\text{Kruskal}\) 是维护一整个生成森林。

其实 \(\text{Prim}\) 就和它稍微有点不同而已，它只是维护了最小生成树的一部分。而且它最开始确定 \(1\) 号节点属于最小生成树。

它每一次找到一条权值最小的，且满足它连接的其中一个点 \(u\) 已经被选入最小生成树里，另一个点 \(v\) 则未被选中的边。

具体实现是这样子的：

维护一个数组 \(dis[\ ]\) ,如果 \(u\) 没有被选入，那么 \(dis[u]\) 就等于 \(u\) 和已经被选中点之间的连边中权值最小的边的权值。

反之 \(dis[u]\) 就等于 \(u\) 被选中的时候选出来那条权值最小边的权值。

然后怎么判是否选中呢？

维护一个\(vis[]\) 即可。然后从 \(vis[]=\text{false}\)的节点中 （也就是未被选中的节点） 选出一个 \(dis[]\) 最小的标记它

然后扫描和这个被选点的所有直接连它的边，更新另外一个端点的 \(dis\) 。

最后生成树的权值和就是 \(\sum\limits^{n}_{i=2} dis[i]\)。

代码：

#include
using namespace std;

const int si=5e3+10;
int n,m;
int a[si][si];
int dis[si];
bool vis[si];

int main(){
	cin>>n>>m;
	memset(a,0x3f,sizeof a);
	for(register int i=1;i<=n;++i){
		a[i][i]=0;
	}
	for(register int i=1,u,v,w;i<=m;++i){
		cin>>u>>v>>w;
		a[v][u]=a[u][v]=min(a[u][v],w);
	}
	//Prim
	memset(dis,0x3f,sizeof dis);
	memset(vis,false,sizeof vis);
	dis[1]=0;
	for(register int i=1,u;i

Boruvka

该算法并不常用，以后有时间会填坑。

例题：

  • P1194 买礼物
  • P1119 灾后重建
  • P1195 口袋的天空
  • P1265 公路修建
  • P1340 兽径管理
  • P1396 营救
  • P1536 村村通
  • P2212 [USACO14MAR]Watering the Fields S
  • P2330 [SCOI2005]繁忙的都市
  • P3366 【模板】最小生成树

Tips

关于Kruskal 算法过程的一个shabi理解

昨天（21/5/17） 晚上yl一直在纠结一道题（CF891C）。

然后在一番讨论之后，我有了一个对于 $\text{Kruskal} $ 的新理解

就是对于原图，我们将它划分为 \(n\) 个相互连通的子集（有多种方式）。

且每一个子集原图的一个生成森林。

然后对于任意两个生成森林之间，我们找出所有连通他们的边。

取出有最小权值的边。

然后对于取出这 \(C^2_n\) 条边，我们从小到大取就行（当然这里是动态过程所以不一定一直是原来最初的划分情况）（直到构成生成树也就是选完所有情况）（算法里的那个for）。

（这里利用并查集判断这个边是不是可以选出来的边（也就是连通两个生成森林的边），从小到大的话就根据最开始的排序来就行）（算法里的for当中的if和最开始的sort）

至于为什么用并查集判是否连通两个森林选出来的那个边一定是连接那两个生成森林的最小边呢？

因为排了序啊，所以我们取到的第一个连通这两个森林的边一定是连通他们的边当中最小的。

（有点混乱但是解释了一点神奇的东西）

对于最小生成树性质的证明：

By ： ciwei

（这位dalao的证明真的很有用！）

原文：

https://zhuanlan.zhihu.com/p/340438116 https://zhuanlan.zhihu.com/p/340411111

gfqd4H.png

引理部分：

gfqaUe.png
gfqUED.png

Prim 的证明

By ： ciwei

原文：https://zhuanlan.zhihu.com/p/340464163

gfLBoF.png
gfL0dU.png

kruskal 的证明

By：ciwei

原文：https://zhuanlan.zhihu.com/p/340628568

gfOVTU.png
gfOEwT.png
gfOekF.png

Reference：

ciwei:最小生成树相关定理和算法正确性证明

Kruskal 重构树

一个神奇的科技，因为 \(\texttt{8102ION}\text{归程}\) 这道出了名的题，而被世人所知（

这个东西基于 \(\texttt{Kruskal}\) 实现。

具有非常多优雅的性质。

做法是在跑 \(\texttt{Kruskal}\) 对于不在同一集合的两个点 \((u,v)\) 连边的时候，我们新建一个节点 \(k\) ，令 \((u,v)\)
分别所在的集合的根 \(r_u,r_v\) 分别作为 \(k\) 的左右儿子。

并且我们把 \(k\) 作为 \(S_u,S_v\) 两个集合合并之后的根。

然后把 \(k\) 的点权置为 \(\delta(u,v)\) 的权值。

跑完 \(\texttt{Kruskal}\) 之后，我们就得到了一颗优美的重构树。

他满足以下性质：

  1. (只考虑新节点)根据构造过程，\(\texttt{Kruskal}\) 重构树是一颗二叉树，并符合二叉堆的性质。
  2. 原来的最小生成树两点间的的最大边权就是 \(\texttt{Kruskal}\) 重构树上两点的 \(\text{Lca}\)的权值。
  3. 重构树中代表原树中的点的节点全是叶子节点，其余节点都代表了一条边的边权。

然后实际上所有新建的点 \(k\) 的含义就是：

如果 \(k\) 的左右子树中的点想要互通，必须要走至少一条边权等于这个点权 \(w_k\) 的边。

有什么用呢？

假设我们一开始的时候从小到大排序，也就是求最小生成树。

那么我们搞出来的重构树上的 \(\text{Lca}(u,v)\) 就代表原图当中 \(u\to v\) 的所有简单路径的边当中的
最大边的最小值。

比如说你原图上 \(1\to 4\) 有两条路径，他们分别是 \(1 \to 2 \to 4,1\to 3 \to 4\)

然后边权是 \(w(1,2)=1,w(1,3)=2,w(3,4)=3,w(2,4)=4\)。

那么第一条路径的最大边是 \(4\) ，第二条的最大边是 \(3\)。

那么 简单路径的边当中的最大边的最小值。这句话的意思就是 \(\min(3,4)=3\)。

推广一下就是 \(\min\limits_{i=1}^{cnt}(\max \{w(uu,vv)\}), (uu,vv \in \forall \delta(u,v))\)

\(cnt\) 是简单路径数。

手元一下：

fzLV6x.png

这个地方是网上很多博客都写错了的，很明显就是直接抄别人的然后一直抄下去搞得很多都是错的（

好像OI wiki 这个时候（21/8/22） 也是错的。

然后最大生成树倒过来就行了。

比如重构树的 \(\text{Lca}(u,v)\) 代表的就是最大生成树上 \((u,v)\) 两点之间路径的小边。

然后原图上就是最小边最大。

来一道题理解：

[NOIP2013]货车运输

A国有 \(n\) 座城市，编号从 \(1\) 到 \(n\)，城市之间有 \(m\) 条双向道路。每一条道路对车辆都有重量限制，简称限重。

现在有 \(q\) 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。

就是 最大生成树 中的 \((u,v)\) 之间的路径的最小边。

代码：

#include
using namespace std;

const int si_n=1e4+10;
const int si_m=5e4+10;
int n,m,q;

struct Kruskal{
	int u,v,w;
	bool operator < (const Kruskal &b)const{
		return w>b.w;
	}//最大生成树
}e[si_m<<1];
int pa[si_n<<1];
int root(int x){
	if(pa[x]!=x) return pa[x]=root(pa[x]);
	return pa[x];
}

struct Tree{
	int ver,head,Next;
}t[si_m<<1];
int cnt=0,tot=n;//一定注意这里赋值时没用的，要在主函数里读入n之后再赋值！
void add(int u,int v){
	t[++cnt].ver=v,t[cnt].Next=t[u].head;
	t[u].head=cnt;
}
int val[si_n<<1];
bool vis[si_n<<1];
int f[si_n<<1][20],dep[si_n<<1];
void dfs(int i,int fa){
    dep[i]=dep[fa]+1;
    f[i][0]=fa,vis[i]=true;
    for(register int j=1;j<18;++j){
        f[i][j]=f[f[i][j-1]][j-1];
    }
    for(register int j=t[i].head;j;j=t[j].Next){
        int v=t[j].ver;
        if(v==fa) continue;
        dfs(v,i);
    }
}

int lca(int u,int v){
    if(dep[u]=0;--i){
        if(dep[f[u][i]]>=dep[v]) u=f[u][i];
    }
    if(u==v) return u;
    for(register int i=19;i>=0;--i){
        if(f[u][i]!=f[v][i]){
            u=f[u][i],v=f[v][i];
        }
    }
    return f[u][0];
}
void insert(int u,int v,int w){
	int k=++tot;val[k]=w;
	int ru=root(u),rv=root(v);
	add(k,ru),add(ru,k);
	add(k,rv),add(rv,k);
	pa[k]=pa[ru]=pa[rv]=k;//先加边后合并
}

int main(){
	memset(vis,false,sizeof vis);
	scanf("%d%d",&n,&m);
	tot=n;// qwq
	for(register int i=1;i<=n;++i){
		pa[i]=i;
	}
	for(register int i=1;i<=m;++i){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		e[i]=(Kruskal){u,v,w};
	}
	sort(e+1,e+1+m);
	for(register int i=1;i<=m;++i){
		int ru=root(e[i].u),rv=root(e[i].v);
		if(ru!=rv) insert(e[i].u,e[i].v,e[i].w);
	}
	for(register int i=1;i<=tot;++i){
		if(!vis[i]) dfs(root(i),0);
	}// 防止不连通
	// for(register int i=1;i<=tot;++i){
		// cout<

然后可以发现这类问题的核心：

若一个点能通过一条路径到达，那么我们走最小（大）生成树上的边也一定能到达该节点。

Reference：

https://www.luogu.com.cn/blog/mywd-ylyy/kruskal-zhong-gou-shu#blog-comments（这一篇有个地方写错了）

https://blog.csdn.net/niiick/article/details/81952126

Algor-并查集Algor-最小生成树Cate-数据结构Type-算法笔记

相关

标签

一品网 冀ICP备14022925号-6