20250814 最小生成树总结

发布于：2025-08-15 ⋅ 阅读:(19) ⋅ 点赞:(0)

引子

啊啊额，从一张图里抽出几条边，组成一棵树，无环n−1n-1n−1条边，就是生成树。那么边权和最小的生成树就叫最小生成树，最大生成树同理。

kruskal最小生成树

要求kruskal最小生成树，我们首先用结构体数组接入数据，然后按照每条边的边权进行升序排序，接着用并查集判断每一条边，看两边的端点是否已经在目前的生成树里连通，否的话就加入这条边，如果目前边数==n−1==n-1==n−1，就breakbreakbreak，在循环外再进行判断，看并查集数组里面是否有两个以上的不同的祖宗，是的话就按题目要求输出，否则输出目前disdisdis数组的总和。

例子

3
1
4
2
1
3
3
A
B
C
D
E

如上图，我们可以知道有以下7条边：

  1. A↔\leftrightarrow↔B，w=3
  2. A↔\leftrightarrow↔C，w=1
  3. A↔\leftrightarrow↔E，w=1
  4. B↔\leftrightarrow↔D，w=4
  5. C↔\leftrightarrow↔D，w=2
  6. C↔\leftrightarrow↔E，w=3
  7. D↔\leftrightarrow↔E，w=3

排完序是这样：

  1. A↔\leftrightarrow↔C，w=1
  2. A↔\leftrightarrow↔E，w=1
  3. C↔\leftrightarrow↔D，w=2
  4. A↔\leftrightarrow↔B，w=3
  5. C↔\leftrightarrow↔E，w=3
  6. D↔\leftrightarrow↔E，w=3
  7. B↔\leftrightarrow↔D，w=4

接下来我们来枚举每一条边，具体过程如下：

  1. A↔\leftrightarrow↔B，此时为空图，直接放进去。
1
A
C
  1. A↔\leftrightarrow↔E，加入后并不形成环，可以放进去。
1
1
A
C
E
  1. C↔\leftrightarrow↔D，放入。
1
1
2
A
C
E
D
  1. A↔\leftrightarrow↔B，也可以放入。
1
1
2
3
A
C
E
D
B

此时，我们已经添加了n−1n-1n−1条边，已经breakbreakbreak了，所以答案算出最终为7。

实现 //////这一段每一行都有注释

//就不给include了
struct edge{//结构体
	int u,v,w;//来点，去点，边权
}a[200005];//结构体数组
bool cmp(edge x,edge y){//结构体排序
	return x.w<y.w;//按照边权排序
}//一个用于排序的函数
int fa[5005],cnt,ans; //并查集数组，已选边数，边权总和
int find(int x){ //并查集必备
	return fa[x]==x?x:fa[x]=find(fa[x]);//顺带更新fa数组
}//一个用于并查集的函数
int kruskal(){//开始最小生成树
	int n,m;//点的数目，边的数目
	cin>>n>>m;//输入数据
	for(int i=1;i<=m;i++){//输入每条边
		cin>>a[i].u>>a[i].v>>a[i].w;//接入结构体数组
	}//第一个循环出现了
	sort(a+1,a+1+m,cmp);//排序
	for(int i=1;i<=n;i++)fa[i]=i;//并查集数组的初始值
	for(int i=1;i<=m;i++){//循环每条边
		int u=a[i].u,v=a[i].v,w=a[i].w;//拿出a[i]
		int u=find(u),v=find(v);//跑一边并查集
		if(u!=v){//如果祖先不相同
			fa[v]=u,cnt++,ans+=w;//v认u做祖宗，边数加一，总和加该边的边权
		}//这是一个if
		if(cnt==n-1){//如果边数达到了n-1
			break;//退出循环
		}//这也是一个if
	}//还有一个循环
	int sum=0;//查看有几个祖宗
	for(int i=1;i<=n;i++){//查看并查集数组
		if(i==fa[i])sum++;//如果这货认自己为祖宗，说明他就是一个祖宗
	}//还有最后的判断
	if(sum>=2){//如果有两个及以上个祖宗，就没戏了
		return -1;//看题目要输出什么就输出什么
	}//快结束了
	return ans;//返回最终结果
}//不要抄袭哦！

kruskal还没有结束，他还有时间复杂度，O(mlogmmlogmmlogm)。//////华丽结束

prim最小生成树

额额啊，你没猜错，还有prim！让我们开始吧！
首先，他非常 常见 好写 简单 易懂；然后实现有点像dij，毕竟都是图论；最后，他是一种基于贪心的算法。为什么这么说呢？因为他每次都是找出一个离生成树距离最小的一个点，然后把该点放入生成树。

过程&例子

俗话说的好，一张图顶一堆话……

3
1
4
2
1
3
3
1
2
3
4
5

dis数组={0，\infty， \infty，\infty，\infty$}

还是这图，但我们这次用prim来写。

最开始，我们把1号点放进生成树，此时生成树和dis长这样：

1

dis数组={0，∞，∞，∞，∞0，\infty， \infty，\infty，\infty0，∞，∞，∞，∞} //////第0轮

然后循环n-1次，每次找出dis数组里值最小且没被选过的一个点，把它拿出来看看他有哪些边，如果连向的点也没被选过，就更新他的dis。生成树和dis依次如下：

1

dis数组={0，3，1，∞，10，3， 1，\infty，10，3，1，∞，1} //////第1轮

1
1
3

dis数组={0，3，1，2，10，3， 1，2，10，3，1，2，1} //////第2轮

1
1
1
3
5

dis数组={0，3，1，2，10，3， 1，2，10，3，1，2，1} //////第3轮

1
1
2
1
3
5
4

dis数组={0，3，1，2，10，3， 1，2，10，3，1，2，1} //////第4轮

最终答案为7。

实现

const int d=1e9;//朴素
struct edge{
	int u,v,w;
};
vector<edge> E[5005];
int dis[5005],n,m;
bool f[5005];
int prim(){
	for(int i=1;i<=n;i++)dis[i]=d;
	dis[1]=0;//千万别忘了
	for(int i=1;i<n;i++){
		int mn=d,u=0;
		for(int k=1;k<=n;k++){
			if(dis[k]<mn&&!f[k]){
				mn=dis[k],u=k;
			}
		} 
		f[u]=1;//把自己加入生成树中
		for(int j=0;j<E[u].size();j++){
			int v=E[u][j].v,w=E[u][j].w;
			if(!f[v]){
				dis[v]=min(dis[v],w);
			}
		}
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		if(dis[i]==d){
			return -1;
		}
		sum+=dis[i];
	}
	return sum;
}

const int dd=1e9;//堆优化
struct node{
    int v,w;
    bool operator<(const node&a)const{
        return w>a.w;
    }
};
int n,m,dis[5005];
bool vis[5005];
vector<node> E[5005];
priority_queue<node> q;
void prim(){
	int cnt=0;
	q.push({1,0});
	while(!q.empty()&&cnt<=n){
		node d=q.top();
		q.pop();
		if(vis[d.v])continue;
		vis[d.v]=1,dis[d.v]=min(dis[d.v],d.w),cnt++;
		for(int i=0;i<E[d.v].size();i++){
			if(!vis[E[d.v][i].v]){
				q.push({E[d.v][i].v,E[d.v][i].w});
			}
		}
	}
}//知道为什么跟dij很像了吧！

等，时 间 复 杂 度！

朴素 O(n2+m^2 + m2+m)
堆优化 O((n+m)logm(n+m)logm(n+m)logm)

kruskal重构树

啊额啊，生成树之后还有重构树，要炸掉了 ! 可恶的kruskal !

重构树，说白了就是把一张图改成一棵树，然后再这棵树上LCA。

过程&例子

嗯？不懂？好吧，我们还是一样来张图：

1
5
3
1
2
4
1
2
3
4
5

首先跟前面kruskal最小生成树的步骤一样，把所有的边按照边权排序。

  1. 1 ↔\leftrightarrow↔ 2，w=1
  2. 2 ↔\leftrightarrow↔ 4，w=1
  3. 3 ↔\leftrightarrow↔ 5，w=2
  4. 1 ↔\leftrightarrow↔ 4，w=3
  5. 5 ↔\leftrightarrow↔ 4，w=4
  6. 1 ↔\leftrightarrow↔ 3，w=5

接着，我们循环把所有的边拿出来，查看他们的祖宗是否相同，否的话就把这条边挂在用于LCA的树上。

咋挂？这时，我们需要扩域，也就是建造虚拟节点，cnt。

循环前把cnt设为n，每次要挂边时，cnt++，然后让cnt当u和v的父亲，同时更新并查集数组和记录每个cnt的左儿子节点和右儿子节点的距离的b数组。

以下为得出的树和各个数组：
6
1
2
7
4
8
3
5
9
1 2 3 4 5 6 7 8 9
fa 6 6 8 7 8 7 9 9 9
b / / / / / 1 1 2 4

现在树建好了，就等着LCA啦！

实现

#include<bits/stdc++.h>
using namespace std;
struct edge{
    int u,v,w;
}a[600005];
bool cmp(edge x,edge y){
    return x.w<y.w;
}
int fa[200005],b[200005],dep[200005],fc[25][200005],cnt;//并查集数组，每个cnt的左儿子节点和右儿子节点的距离，深度，次方父亲数组
vector<int> E[200005];
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void dfs(int x,int f){
    dep[x]=dep[f]+1;
    for(int i=1;i<=20;i++)fc[i][x]=fc[i-1][fc[i-1][x]];
    for(int i=0;i<E[x].size();i++){
        int v=E[x][i];
        if(v==f)continue;
        fc[0][v]=x;
        dfs(v,x);
    }
}
int LCA(int x,int y){
    if(dep[x]>dep[y]){
        swap(x,y);
    }
    for(int i=19;i>=0;i--){
        if(dep[fc[i][y]]>=dep[x]){
            y=fc[i][y];
        }
    }
    if(x==y)return x;
    for(int i=19;i>=0;i--){
        if(fc[i][x]!=fc[i][y]){
            x=fc[i][x];
            y=fc[i][y];
        }
    }
    return fc[0][x];
}
int main(){
    int n,m;
    cin>>n>>m;
    cnt=n;
    for(int i=1;i<=m;i++){
        cin>>a[i].u>>a[i].v>>a[i].w;
    }
    sort(a+1,a+1+m,cmp);
    for(int i=1;i<=n*2;i++)fa[i]=i;//由于进行了扩域，所以*2
    for(int i=1;i<=m;i++){//把所有边拿出来瞅瞅
        int u=a[i].u,v=a[i].v,w=a[i].w;
        u=find(u),v=find(v);
        if(u!=v){
            fa[v]=fa[u]=++cnt;
            b[cnt]=w;
            E[u].push_back(cnt);
            E[v].push_back(cnt);
            E[cnt].push_back(u);
            E[cnt].push_back(v);
        }
    }
    for(int i=1;i<=cnt;i++){//一系列LCA
        if(i==fa[i]){
            dfs(i,0);
        }
    }
    int q;
    cin>>q;
    while(q--){//q次询问
        int x,y;
        cin>>x>>y;
        if(find(x)!=find(y)){
            cout<<"impossible"<<endl;
        }else{
            cout<<b[LCA(x,y)]<<endl;
        }
    }
	return 0;
}

俗话说得好，所有的代码都可以缩成两行。

#include<bits/stdc++.h> //献上最后的代码
using namespace std;struct edge{int u,v,w;}a[600005];vector<int> E[200005];int fa[200005],b[200005],dep[200005],fc[25][200005],cnt,n,m,q;bool cmp(edge x,edge y){return x.w<y.w;}int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}void dfs(int x,int f){for(int i=1;i<=20;i++){fc[i][x]=fc[i-1][fc[i-1][x]],dep[x]=dep[f]+1;}for(int i=0;i<E[x].size();i++){int v=E[x][i];if(v==f){continue;}else{fc[0][v]=x,dfs(v,x);}}}int LCA(int x,int y){if(dep[x]>dep[y])swap(x,y);for(int i=20;i>=0;i--){if(dep[fc[i][y]]>=dep[x])y=fc[i][y];}if(x==y)return x;for(int i=20;i>=0;i--){if(fc[i][x]!=fc[i][y])x=fc[i][x],y=fc[i][y];}return fc[0][x];}int main(){cin>>n>>m;for(int i=1;i<=m;i++){cin>>a[i].u>>a[i].v>>a[i].w;}sort(a+1,a+1+m,cmp);for(int i=1;i<=n*2;i++)fa[i]=i,cnt=n;for(int i=1;i<=m;i++){int u=a[i].u,v=a[i].v,w=a[i].w,fu=find(u),fv=find(v);if(fu!=fv)fa[fu]=fa[fv]=++cnt,b[cnt]=w,E[cnt].push_back(fu),E[cnt].push_back(fv),E[fu].push_back(cnt),E[fv].push_back(cnt);}for(int i=1;i<=cnt;i++)if(fa[i]==i)dfs(i,0);cin>>q;while(q--){int x,y;cin>>x>>y;find(x)!=find(y)?cout<<"impossible\n":cout<<b[LCA(x,y)]<<endl;}return 0;}

完结万岁！！！

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布