

最小生成树

Copyright

本页面贡献者：zrz。本页面内容遵循 MIT 协议，转载请附上原文出处链接和本声明。

在学习之前，请确保明确一下定义：

1.树 2.生成树

最小生成树¶

最小生成树：我们定义无向连通图的最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。

注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。

Kruskal 算法¶

最为常用的最小生成树写法

思想：贪心的加边复杂度： $O(mlog(m))$ 适用条件：适用于稀疏图

给定n个点的图和若干条边，首先将所有边按边权从小到大排序，在将图中所有边清空，枚举每一条排好序的边，将边加入图中，若是成环，则不能加这条边，若是无环，就加上这条边，一直加到图中有n-1条边为止。可以证明最后的图为原图的最小生成树。

参考代码： 注意需要并查集实现

struct nod{
    int u,v,w;
}e[200005];//这里不是前向行的存边方法，只是正长的存边
bool cmp(nod a ,nod b){
    return a.w<b.w;
}
int fa[maxn];
int get(int x){
    if(fa[x]==x)return x;
    else return fa[x]=get(fa[x]);
}
bool merge(int x,int y){
    int p = get(x);
    int q = get(y);
    if(p!=q){
        fa[p] = q;
        return true;
    }
    return false ;
}

主函数部分

sort(e,e+m,cmp);//贪心的排序
int ans=0,cnt=0;
for(int i=0;i<m;i++){
    if(cnt==n-1)break;
    else if(merge(e[i].u,e[i].v)){
        cnt++;
        ans+=e[i].w;

    }
}

Prime算法¶

思想：贪心的加点复杂度： $O((n+m)log(n))$ 适用条件：适用于稠密图

注意如果我们暴力维护的复杂度是 $O(n^2+m)$ 这里采用了堆优化,大家可以类比Dijkstra的堆优化去理解

维护了一个选取点的集合，然后每次找出离这个集合中所有点中最近的一个点加入该集合，最终得到最小生成树。

参考代码：

struct Node{
    int pos,val;
    bool operator < (const Node & a) const{
        return a.val<val;
    } 
};
priority_queue<Node> q;
int dis[105];
void Prime(int s){
    Node x,y;
    dis[s]=0;
    x.val=dis[s];x.pos=s;
    q.push(x);
    do{
        x=q.top();q.pop();
        int u=x.pos;
        sum+=dis[u];
        dis[u]=0;
        for(int i=1;i<=n;i++){
            if(Map[u][i]+dis[u]<dis[i]){
                dis[i]=Map[u][i]+dis[u];
                y.val=dis[i];
                y.pos=i;
                q.push(y);
            }
        }
    }while(!q.empty());
}

次小生成树¶

非严格次小生成树¶

在无向图中，边权和最小的满足边权和大于等于 最小生成树边权和的生成树

求解方法¶

求出无向图的最小生成树 $T$ ，设其权值和为 $M$
遍历每条未被选中的边e{u,v,w}，找到 $T$ 中 $u$ 到 $v$ 路径上边权最大的一条边 $e'={s,t,w'}$ ，则在 $T$ 中以 $e$ 替换 $e'$ ，可得一棵权值和为 $M' = M + w - w'$ 的生成树 $T'$ .
对所有替换得到的答案 $M'$ 取最小值即可

我们可以使用倍增来维护，预处理出每个节点的 $2^i$ 级祖先及到达其 $2^i$ 级祖先路径上最大的边权，这样在倍增求LCA的过程中可以直接求得。

严格次小生成树¶

在无向图中，边权和最小的满足边权和严格大于最小生成树边权和的生成树

考虑刚才的非严格次小生成树求解过程，为什么求得的解是非严格的？

因为最小生成树保证生成树中 $u$ 到 $v$ 路径上的边权最大值一定不大于 $u$ 其他从 $v$ 到路径的边权最大值。换言之，当我们用于替换的边的权值与原生成树中被替换边的权值相等时，得到的次小生成树是非严格的。

解决的办法很自然：我们维护到 $2^i$ 级祖先路径上的最大边权的同时维护 严格次大边权，当用于替换的边的权值与原生成树中路径最大边权相等时，我们用严格次大值来替换即可。

这个过程可以用倍增求解，复杂度 $O(mlog(m))$ 。

瓶颈生成树¶

无向图 $G$ 的瓶颈生成树是这样的一个生成树，它的最大的边权值在 $G$ 的所有生成树中最小。

性质¶

最小生成树是瓶颈生成树的充分不必要条件。即最小生成树一定是瓶颈生成树，而瓶颈生成树不一定是最小生成树。

problem

POJ 2395 Out of Hay 求最小生成树解决

最小瓶颈路¶

无向图 $G$ 中 x 到 y 的最小瓶颈路是这样的一类简单路径，满足这条路径上的最大的边权在所有 x 到 y 的简单路径中是最小的。

根据最小生成树定义，x 到 y 的最小瓶颈路上的最大边权等于最小生成树上 x 到 y 路径上的最大边权。虽然最小生成树不唯一，但是每种最小生成树 x 到 y 路径的最大边权相同且为最小值。也就是说，每种最小生成树上的 x 到 y 的路径均为最小瓶颈路。

但是，并不是所有最小瓶颈路都存在一棵最小生成树满足其为树上 x 到 y 的简单路径。

例如下图：

1 到 4 的最小瓶颈路显然有以下两条：1-2-3-4。1-3-4。

但是，1-2 不会出现在任意一种最小生成树上。

应用¶

由于最小瓶颈路不唯一，一般情况下会询问最小瓶颈路上的最大边权。也就是说，我们需要求最小生成树链上的 $max$ 。倍增、树剖都可以解决，这里不再展开。

参考资料¶

图论 OI Wiki