【算法笔记】最小生成树

前言

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

所以现在有时间了。

回来写一写。

最小生成树

定义：

简单来说，最小生成树是一张带权无向图里面由全部 $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<bits/stdc++.h>
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<u.val;
    }
}ed[si];

int root(int x){
    if(pa[x]!=x) pa[x]=root(pa[x]);
    return pa[x];
}

bool Union(int x,int y){
    int rx=root(x),ry=root(y);
    if(rx==ry){
        return 0;
    }
    pa[rx]=ry;
    return 1;
}

int main(){
    cin>>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<<ans<<endl;
    return 0;
}

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^{n}_{i=2} dis[i]$。

代码：



#include<bits/stdc++.h>
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<n;++i){
		u=0;
		for(register int j=1;j<=n;++j){
			if(!vis[j]&&(u==0||dis[j]<dis[u])) u=j;
		}
		vis[u]=1;
		for(register int v=1;v<=n;++v){
			if(!vis[v]) dis[v]=min(dis[v],a[u][v]);
		}
	}
	//answer
	int ans=0;
	for(register int i=2;i<=n;++i){
		ans+=dis[i];
	}
	cout<<ans<<endl;
	return 0;
}