Kruskal 算法求最小生成树与次小生成树

文章目录

• Kruskal 算法
  • 做法
  • 证明
• 次小生成树
  • 参考代码
• 参考

Kruscal 算法是求最小生成树的基础算法，很容易求得最小生成树，但是怎么利用这个算法求非严格次小生成树与严格次小生成树呢？

Kruskal 算法

做法

这个算法很基础，也很好理解，首先对所有边的权值从小到大排序（既然是要求最小生成树），从边权最小的边开始枚举，对于每条边，如果其两个端点目前不联通，则加入这条边，否则说明加入这条边会成环，就不加。“加入这条边”的操作（也就是合并联通块）用并查集解决。

证明

（其实这个算法 yy 一下就大概知道了……）

Wikipedia 上说：

可以用反证法：如果这条边不在最小生成树中，它连接的两个连通分量最终还是要连起来的，通过其他的连法，那么另一种连法与这条边一定构成了环，而环中一定有一条权值大于这条边的边，用这条边将其替换掉，图仍旧保持连通，但总权值减小了。也就是说，如果不选取这条边，最后构成的生成树的总权值一定不会是最小的。

讲得详细点：
假设按照 Kruskal 算法加入的边集为 $e_1,e_2,e_3,\dots,e_{m-1},e_m$ ，形成了树 $T_1$；
（用反证法）假设这时候求得的 $T_1$ 不是该图的最小生成树，则存在最小生成树 $T_2$；假设其边集为 $p_1,p_2,p_3,\dots,p_{m-1},p_m$；
那么这两个集合有一个前缀是相同的（可能前缀长度为0），即 $e_1=p_1,e_2=p_2,\dots,e_{k-1}=p_{k-1}$，直到 $p_k > e_k$。
假设现在我们强制把 $e_k$ 也加入 $T_2$，那么现在一定会形成一个环，这个环里 $p_k > e_k$，也就是说把 $p_k$ 去掉会形成一棵更小的生成树。
说明前面的假设错误，证得这时 $T_1$ 是最小生成树。

次小生成树

先介绍一种超级暴力的做法，枚举最小生成树（MST）上的边，把这条边去掉重新跑 MST……

现在怎么用 Kruskal 求次小生成树呢？首先说说非严格次小生成树的做法（所谓非严格次小生成树，就是可能有多个最小生成树的情况下次小生成树可以被认为是最小生成树）。

在 Kruskal 算法里我们可以标记哪些边在 MST 里，那么现在我们可以枚举每条不在 MST 上的边，考虑把这条边加入的情况。
显然，加入这条边会形成环。我们要求的可是次小生成树，可仍然是一棵树。那么在加入这条边后形成的环里，我们肯定要去掉一条边。去掉那条边呢？
假设去掉边 $e_k$ ，加入 $p_k$ ，为了确保我们得到的是次小生成树，我们要使 $p_k-e_k$ 最小（显然 $p_k \geqslant e_k$）。所以对于每个 $p_k$，让 $e_k$ 尽量大就可以了，换句话说我们要找到加入 $p_k$ 所在的环里的最大边，替换之，看看答案。最后找到最接近最小生成树的答案就可以了。
如何实现“加入 $p_k$ 所在的环里的最大边”这一神奇的操作呢？用树上倍增（类似 LCA 的做法）就可以了。

再考虑严格次小生成树的做法。我们需要确保 “加入 $p_k$ 所在的环里的最大边” 不与 $p_k$ 相同，多写一个特殊判断的 DFS 就可以实现了。

参考代码

洛谷模板题：P4180 【模板】严格次小生成树[BJWC2010]

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100005,maxe=300005;
int n,m,fa[maxn],f[maxn][18],to[maxn][18],deep[maxn];
int tot=0,lnk[maxn],nxt[maxe*2],son[maxe*2],w[maxe*2];
bool vis[maxn];
long long ans=(long long)1<<60,sum=0;
struct SideData{
    int x,y,w;
    bool used;
}a[maxe];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline bool cmp(SideData aa,SideData bb){
    return aa.w<bb.w;
}
inline void add(int x,int y,int z){
    tot++;son[tot]=y;w[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;
}
inline int getfa(int x){
    if (fa[x]==x) return x;
    fa[x]=getfa(fa[x]);
    return fa[x];
}
inline void Kruscal(){
    for (int i=1;i<=n;i++) fa[i]=i;
    int cnt=0;
    for (int i=1;i<=m&&cnt<n-1;i++){
        int fx=getfa(a[i].x),fy=getfa(a[i].y);
        if (fx==fy) continue;
        cnt++;a[i].used=1;sum+=(long long)a[i].w;
        fa[fx]=fy;
        add(a[i].x,a[i].y,a[i].w);
        add(a[i].y,a[i].x,a[i].w);
    }
}
inline void Build(int x,int id,int lst){
    vis[x]=1;
    f[x][0]=w[id];to[x][0]=lst;
    for (int i=1;i<18;i++) f[x][i]=max(f[x][i-1],f[to[x][i-1]][i-1]),to[x][i]=to[to[x][i-1]][i-1];
    for (int i=lnk[x];i;i=nxt[i]) if (!vis[son[i]]) deep[son[i]]=deep[x]+1,Build(son[i],i,x);
}
inline int Query(int x,int y){
    //printf("Query: %d %d => ",x,y);
    int ret=0;
    if (deep[x]<deep[y]) swap(x,y);
    for (int i=17;i>=0;i--) if (deep[to[x][i]]>=deep[y]) ret=max(ret,f[x][i]),x=to[x][i];
    for (int i=17;i>=0;i--) if (to[x][i]!=to[y][i]) ret=max(ret,max(f[x][i],f[y][i])),x=to[x][i],y=to[y][i];
    ret=max(ret,max(f[x][0],f[y][0]));
    //printf("%d %d\n",x,y);
    return ret;
}
inline int ExQuery(int x,int y,int z){
    int ret=0;
    if (deep[x]<deep[y]) swap(x,y);
    for (int i=17;i>=0;i--) if (deep[to[x][i]]>=deep[y]){
        if (f[x][i]!=z) ret=max(ret,f[x][i]);
        x=to[x][i];
    }
    for (int i=17;i>=0;i--) if (to[x][i]!=to[y][i]){
        if (f[x][i]!=z) ret=max(ret,f[x][i]);
        if (f[y][i]!=z) ret=max(ret,f[y][i]);
        x=to[x][i];y=to[y][i];
    }
    if (f[x][0]!=z) ret=max(ret,f[x][0]);
    if (f[y][0]!=z) ret=max(ret,f[y][0]);
    return ret;
}
int main(){
    n=read();m=read();
    for (int i=1;i<=m;i++) a[i].x=read(),a[i].y=read(),a[i].w=read();
    sort(a+1,a+1+m,cmp);
    Kruscal();
    deep[1]=1;
    Build(1,0,0);
    for (int i=1;i<=m;i++) if (!a[i].used){
        int qry=Query(a[i].x,a[i].y);
        if (qry==a[i].w) qry=ExQuery(a[i].x,a[i].y,qry);
        long long now=sum-(long long)qry+(long long)a[i].w;
        if (now>sum) ans=min(ans,now);
    }
    printf("%lld\n",ans);
    return 0;
}

参考

Kruskal's algorithm - Wikipedia
（维基百科英文版解禁了吗？！不用魔法居然可以访问……）
克鲁斯克尔算法 - 维基百科，自由的百科全书