专栏文章

8.14最小生成树总结

llyxqqq1
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioc38sv
此快照首次捕获于
2025/12/02 16:46
3 个月前
此快照最后确认于
2025/12/02 16:46
3 个月前
查看原文

最小生成树：功能与算法解析

引言

在图论中，最小生成树（Minimum Spanning Tree, MST） 是一个经典问题，广泛应用于网络设计、交通规划、聚类分析等领域。它的目标是在一个带权无向连通图中找到一棵生成树，使得所有边的权值之和最小。本文将介绍最小生成树的核心功能、常见算法及其特点，帮助读者深入理解其原理与应用。

最小生成树的功能

最小生成树的主要功能可以概括为以下三点：
  1. 连通所有节点
    • 使用最少的边（(V−1(V-1) 条，其中 (V(V) 是顶点数）连接图中的所有顶点，确保无环（形成树结构）。
    • 适用于需要低成本连接所有节点的问题，如城市道路规划、通信网络布线等。
  2. 最小化总权重
    • 在所有可能的生成树中，MST 的边权总和是最小的，确保资源的最优分配。
  3. 典型应用场景
    • 网络设计：如光纤布线、电力网络优化，降低建设成本。
    • 交通规划：寻找连接多个城市的最低成本公路或铁路方案。
    • 数据聚类：在机器学习中，利用 MST 进行层次聚类或图像分割。

最小生成树的算法

目前，最常用的两种 MST 算法是 Prim 算法 和 Kruskal 算法，它们均采用贪心策略，但实现方式不同。

1. Prim 算法

核心思想：
  • 从任意一个顶点开始，逐步扩展生成树，每次选择连接当前树与非树节点的最小权边。
特点：
  • 适合稠密图（边较多），使用邻接矩阵时时间复杂度为 (O(V2)(O(V^2))，若采用优先队列优化可降至 (O(ElogV)(O(E log V))。
  • 始终保持树的连通性，适用于需要逐步构建 MST 的场景。
执行步骤：
  1. 初始化一个 MST，从任意节点开始。
  2. 每次选择连接树与非树节点的最小权边，并将新节点加入树。
  3. 重复直到所有节点都被包含。

2. Kruskal 算法

核心思想：
  • 将所有边按权值从小到大排序，依次选择边加入 MST，确保不形成环，直到选够 (V−1(V-1) 条边。
特点：
  • 适合稀疏图（边较少），时间复杂度主要由排序决定（(O(ElogE(O(E log E))）。
  • 使用并查集（Disjoint Set Union, DSU） 高效检测环路。
执行步骤：
  1. 对所有边按权值升序排序。
  2. 依次选择最小边，若其两个端点不在同一集合（不形成环），则加入 MST。
  3. 重复直到 MST 包含 (V−1(V-1) 条边。

3. 其他算法与优化

除了 Prim 和 Kruskal，还有一些变种算法：
  • Borůvka 算法：
    • 适用于并行计算，每轮为每个连通分量选择最小边，时间复杂度 (O(ElogV)(O(E log V))。
  • 反向删除算法：
    • 从完整图开始，逐步删除最大权边（保持连通），直到剩下 (V−1(V-1) 条边。

最小生成树的性质

  1. 切割性质（Cut Property）
    • 在图的任意切割（将节点分成两个集合）中，横跨切割的最小权边一定属于 MST。
  2. 环路性质（Cycle Property）
    • 如果某条边在一个环路中是最大权边，那么它一定不在 MST 中。
这些性质保证了 Prim 和 Kruskal 算法的正确性，并可用于优化或验证 MST。

总结

最小生成树是解决最优连通问题的关键工具，Prim 和 Kruskal 算法是其中最经典的两种实现方式：
  • Prim 适合稠密图，采用节点扩展策略。
  • Kruskal 适合稀疏图，采用边排序策略。
选择合适的算法取决于图的规模与结构，而理解其核心思想有助于优化实际应用中的计算效率。 ---------------不优美的分界线------------------
题目号时间复杂度空间复杂度思路
AO(m+ma(n)m+ma(n))O(n+mn+m)求联通
BO(nlogmnlogm)O(n+mn+m)最小生成树
CO(n2lognn^2logn)O(n2n^2)变形最小生成树
DO(mlogmmlogm)O(m+nm+n))最大生成树
EO(n2lognlogmn^2log nlogm)O(m2m^2)
FO(mlogmmlogm)O(n+mn+m)瓶颈最小生成树
GO(n2lognn² log n)O(n2n^2)二维建边
HO(mlogmmlogm)O(n+mn+m)重构树+LCA
A-H的CODE
A.
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct N{
	int x,y;
}e[200005];
int n,m,cnt,sum,fa[200005];
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x] = find(fa[x]);
}
void un(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x!=y)
		fa[x]=y;
	return ;
}
signed main()
{
    while(1)
    {
    	cin>>n;
        if(n==0)
            return 0;
        cin>>m;
    	for(int i=1;i<=n;i++)
            fa[i]=i;
        for(int i=1;i<=m;i++)
    	{
        	cin>>e[i].x>>e[i].y;
    	    un(e[i].x,e[i].y);
        }
        sum=0;
        for(int i=1;i<n;i++)
        {
            if(find(i)!=find(i+1))
            {
                un(i,i+1);
                sum++;
            }
        }
    	cout<<sum<<endl;
    }
    return 0;
}
B.
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct N{
	int x,y,w;
}e[200005];
int n,m,cnt,sum,fa[200005];
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x] = find(fa[x]);
}
void un(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x!=y)
		fa[x]=y;
	return ;
}
int cmp(N x,N y)
{
	return x.w<y.w;
}
void k()
{
	for(int i=1;i<=n;i++)
		fa[i]=i;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int x=find(e[i].x),y=find(e[i].y);
		if(x==y)
			continue;
		sum+=e[i].w;
		un(x,y);
		cnt++;
		if(cnt==n-1)
			return ;
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>e[i].x>>e[i].y>>e[i].w;
	k();
	if(cnt<n-1)
		cout<<"orz";
	else
		cout<<sum;
	return 0;
}
C.
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct N{
	int x,y,w;
}e[200005];
int n,m,cnt,sum,fa[200005];
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x] = find(fa[x]);
}
void un(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x!=y)
		fa[x]=y;
	return ;
}
int cmp(N x,N y)
{
	return x.w<y.w;
}
void k()
{
	for(int i=1;i<=n;i++)
		fa[i]=i;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int x=find(e[i].x),y=find(e[i].y);
		if(x==y)
			continue;
		sum+=e[i].w;
		un(x,y);
	}
}
signed main()
{
	cin>>n;
	m=0;
	for(int i=1;i<=n;i++)
	{
	    for(int j=1;j<=n;j++)
	    {
	        int x;
	        cin>>x;
	        e[++m].x=i,e[m].y=j,e[m].w=x;
	    }
	}
	k();
	cout<<sum;
	return 0;
}
D.
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct N{
	int x,y,w;
}e[200005];
int n,m,cnt,sum,fa[200005];
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x] = find(fa[x]);
}
void un(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x!=y)
		fa[x]=y;
	return ;
}
int cmp(N x,N y)
{
	return x.w>y.w;
}
void k()
{
	for(int i=1;i<=n;i++)
		fa[i]=i;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int x=find(e[i].x),y=find(e[i].y);
		if(x==y)
			continue;
		sum+=e[i].w;
		un(x,y);
		cnt++;
		if(cnt==n-1)
			return ;
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
	    cin>>e[i].x>>e[i].y>>e[i].w;
	}
	k();
	if(cnt<n-1)
		cout<<"-1";
	else
		cout<<sum;
	return 0;
}
E.
CPP
#include<bits/stdc++.h>
using namespace std;
struct N{
	int x,y;
	double w;
}e[1000005];
struct M{
	int x,y;
}a[505];
int s,n,fa[100005],cnt,m,x[1000005],y[1000005];
double sum;
double dis(int i, int j)
{
	double t1 = (a[i].x - a[j].x) * (a[i].x - a[j].x);
	double t2 = (a[i].y - a[j].y) * (a[i].y - a[j].y);
	return sqrt(t1 + t2);
}
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x] = find(fa[x]);
}
void un(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x!=y)
		fa[x]=y,cnt++;
	return ;
}
int cmp(N x,N y)
{
	return x.w<y.w;
}
void c()
{
	for(int i=1;i<=m;i++)
		fa[i]=i;
	sort(e+1,e+n+1,cmp);
	for(int i=1;i<=n;i++)
	{
		int x=find(e[i].x),y=find(e[i].y);
		if(x==y)
			continue;
		un(x,y);
		if(cnt==m-s)
		{
			printf("%.2lf",e[i].w);
			return ;
		}
	}
}
signed main()
{
	cin>>s>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].x>>a[i].y;
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=i+1;j<=m;j++)
		{
			e[++n].x=i;
			e[n].y=j;
			e[n].w=dis(i,j);
		}
	}
	c();
	return 0;
}
F.
CPP
#include<bits/stdc++.h>
$#define int long long
using namespace std;
struct N{
	int x,y,w;
}e[200005];
int n,m,cnt,sum,fa[200005];
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x] = find(fa[x]);
}
void un(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x!=y)
		fa[x]=y;
	return ;
}
int cmp(N x,N y)
{
	return x.w<y.w;
}
void k()
{
	for(int i=1;i<=n;i++)
		fa[i]=i;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int x=find(e[i].x),y=find(e[i].y);
		if(x==y)
			continue;
		sum=max(sum,e[i].w);
		un(x,y);
		cnt++;
		if(cnt==n-1)
			return ;
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
	    cin>>e[i].x>>e[i].y>>e[i].w;
	}
	k();
	cout<<cnt<<" "<<sum;
	return 0;
}
G.
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct N{
	int x,y,w;
}e[2500005];
int n,m,cnt[250005],sum,a[505][505],fa[250005];
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x] = find(fa[x]);
}
void un(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x!=y)
		fa[x]=y;
	return ;
}
int cmp(N x,N y)
{
	return x.w<y.w;
}
int get_id(int x,int y)
{
    return (x-1)*n+y;
}
void k()
{
	for(int i=1;i<=n*n;i++)
		fa[i]=i,cnt[i]=1;
	sort(e+1,e+m+1,cmp);
	sum=0;
	for(int i=1;i<=m;i++)
	{
		int x=find(e[i].x),y=find(e[i].y);
		if(x==y)
			continue;
		cnt[y]+=cnt[x];
		un(x,y);
		if(cnt[y]>=(n*n+1)/2)
		{
		    cout<<e[i].w<<endl;
		    return ;
		}
	}
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
	    for(int j=1;j<=n;j++)
	    {
	       cin>>a[i][j];
	    }
	}
	for(int i=1;i<=n;i++)
	{
	    for(int j=1;j<=n;j++)
	    {
	       if(i>1)
	       e[++m].x=get_id(i-1,j),e[m].y=get_id(i,j),e[m].w=abs(a[i][j]-a[i-1][j]);
           if(j<n)
           e[++m].x=get_id(i,j+1),e[m].y=get_id(i,j),e[m].w=abs(a[i][j]-a[i][j+1]);
           if(j>1)
           e[++m].x=get_id(i,j-1),e[m].y=get_id(i,j),e[m].w=abs(a[i][j]-a[i][j-1]);
           if(i<n)
           e[++m].x=get_id(i+1,j),e[m].y=get_id(i,j),e[m].w=abs(a[i][j]-a[i+1][j]); 
	    }
	}
	k();
    return 0;
}
H.
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct N{
	int x,y,w;
}e[200005];
int n,m,cnt,a[200005],sum,fa[200005];
int find(int x)
{
	if(fa[x]==x)
		return x;
	return fa[x] = find(fa[x]);
}
void un(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x!=y)
		fa[x]=y;
	return ;
}
int cmp(N x,N y)
{
	return x.w<y.w;
}
void k()
{
	for(int i=1;i<=n;i++)
		fa[i]=i;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		int x=find(e[i].x),y=find(e[i].y);
		if(x==y)
			continue;
		sum+=e[i].w;
		un(x,y);
		cnt++;
		if(cnt==n-1)
			return ;
	}
}
signed main()
{
	cin>>n>>m;
	int mini=1e18;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		mini=min(mini,a[i]);
	}
	for(int i=1;i<=m;i++)
	{
		cin>>e[i].x>>e[i].y>>e[i].w;
		e[i].w*=2;
		e[i].w+=a[e[i].x]+a[e[i].y];
	}
	k();
	cout<<sum+mini;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...