8.14最小生成树总结

lyxqqq1 · 2025-08-14 19:55:02 · 个人记录

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

引言

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

最小生成树的功能

最小生成树的主要功能可以概括为以下三点：

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

最小生成树的算法

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

1. Prim 算法

核心思想：

从任意一个顶点开始，逐步扩展生成树，每次选择连接当前树与非树节点的最小权边。

特点：

适合稠密图（边较多），使用邻接矩阵时时间复杂度为 (O(V^2))，若采用优先队列优化可降至 (O(E log V))。
始终保持树的连通性，适用于需要逐步构建 MST 的场景。

执行步骤：

初始化一个 MST，从任意节点开始。
每次选择连接树与非树节点的最小权边，并将新节点加入树。
重复直到所有节点都被包含。

2. Kruskal 算法

核心思想：

将所有边按权值从小到大排序，依次选择边加入 MST，确保不形成环，直到选够 (V-1) 条边。

特点：

适合稀疏图（边较少），时间复杂度主要由排序决定（(O(E log E))）。
使用并查集（Disjoint Set Union, DSU） 高效检测环路。

执行步骤：

对所有边按权值升序排序。
依次选择最小边，若其两个端点不在同一集合（不形成环），则加入 MST。
重复直到 MST 包含 (V-1) 条边。

3. 其他算法与优化

除了 Prim 和 Kruskal，还有一些变种算法：

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

最小生成树的性质

切割性质（Cut Property）
- 在图的任意切割（将节点分成两个集合）中，横跨切割的最小权边一定属于 MST。
环路性质（Cycle Property）
- 如果某条边在一个环路中是最大权边，那么它一定不在 MST 中。

这些性质保证了 Prim 和 Kruskal 算法的正确性，并可用于优化或验证 MST。

总结

最小生成树是解决最优连通问题的关键工具，Prim 和 Kruskal 算法是其中最经典的两种实现方式：

Prim 适合稠密图，采用节点扩展策略。
Kruskal 适合稀疏图，采用边排序策略。

选择合适的算法取决于图的规模与结构，而理解其核心思想有助于优化实际应用中的计算效率。 ---------------不优美的分界线------------------

题目号	时间复杂度	空间复杂度	思路
A	O(m+ma(n))	O(n+m)	求联通
B	O(nlogm)	O(n+m)	最小生成树
C	O(n^2logn)	O(n^2)	变形最小生成树
D	O(mlogm)	O(m+n))	最大生成树
E	O(n^2log nlogm)	O(m^2)
F	O(mlogm)	O(n+m)	瓶颈最小生成树
G	O(n² log n)	O(n^2)	二维建边
H	O(mlogm)	O(n+m)	重构树+LCA

A-H的CODE

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}

#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;
}