生成树

Vision271 · 2022-09-29 14:48:17 · 个人记录

概述

• 无向连通图 G 的生成树 T 指的是 G 的一个生成子图（即 G.V=T.V），且 T 是一棵树。

• 一般我们主要研究最小生成树问题，即边权总和最小的生成树。

• 需要指出的是，单源最短路算法中用到的所有边恰好也是一棵生成树（可以认为以 s 为根），通常称为最短路树。

最小生成树

Kruskal 算法

• Kruskal 算法的核心思路是按边权贪心。

• 具体来讲，就是给所有边按照边权不降序排序，从小到大贪心地考虑每一条边。

• 如果对应边的两个端点不同属一个连通块，那么将这条边选入生成树，并更新连通块情况。

• 证明：考虑使用反证法。

  • 考虑第 i 条边，如果它能够被加入，则此时加它一定不构成环。

  • 不加它，继续考虑后面的边，构成任意的一棵生成树。我们只需要证明把它加回来更优。

  • 直接把它加上，此时一定构成一个环（否则不符合生成树定义）。

  • 既然当初加它不构环，现在构环，则环上一定有至少一条边是在考虑完它之后被加进来的。

  • 删掉那条边。显然，仍然是一棵生成树，且总边权不增（有可能降）。得证。

• 容易证明复杂度为 O(m\log m)。并查集复杂度大约在 O(m\alpha)，可以忽略不计。

il void kruskal(){
    sort(b+1,b+m+1,cmp);
    int fau,fav;
    For(i,1,m){
        fau=find(b[i].u),fav=find(b[i].v);
        if(fau==fav) continue;
        ans+=b[i].w,merge(fau,fav);
    }
    return;
} 

Prim 算法

memset(dis,127,sizeof(dis));
dis[1]=0;
For(i,1,n){
        int c=2139062143,add;
        For(i,1,n)
            if(!in[i])
                if(c>dis[i]) c=dis[i],add=i;
        ans+=c,in[add]=1;
        For(i,1,n)
            if(!in[i])
                dis[i]=min(dis[i],e[add][i]);
    }

• Prim 算法的核心思路是按到连通块距离贪心。

• 具体来讲，流程如下：

  • 1.任意选一个点 s 作为初始连通块。

  • 2.找在连通块外且到连通块的距离最小的点。

  • 3.加上这个点，更新连通块，更新其他点的距离（枚举出边）。

  • 4.如果连通块大小为 n 那么结束，否则返回第 2 步。

• 可以用类似 Kruskal 的证明方法：如果选了一个非最小，选最小可以构环，然后删掉非最小，结果不会更劣。

• 显然朴素实现的复杂度是 O(n^2+m)。

• 在稀疏图中，可以把 dis 数组用小根堆优化到 O(m\log m) ，但优化后的表现还是不如 Kruskal。

• 主要应用是在稠密图中。此时，不优化的 Prim 表现优于 Kruskal。

次小生成树

• 先做最小生成树，然后枚举不在树里的边以构环，删掉环中第二大的边（也就是原本的最大边）。

• 如果要求严格次小的话，还需考虑删完之后总边权是否真的变大了。可以参考 \text{P4180 [BJWC2010] 严格次小生成树}。

Kruskal 重构树

• 有时题目会有一些限制，譬如：

  • 只允许经过边权大于/小于 x 的边。

  • 只允许在时间 t 后经过边 (u,v)。

  • 只在时间 t 后，元素 (u,v) 有关系。

• 此时考虑把边按权（时间也是权）排序依次加上去。不同的是，我们不再直接加边：

  • 考虑边 (u,v)，我们找到它们在重构树上的代表结点 fau,fav。

  • 建立一个新的虚点 w，让 fau,fav 认 w 为父。fau,fav 的代表结点也变成 w。

  • 没错，就是定向并查集（不用担心这个的复杂度。Tarjan 证明过，这个定向并查集的复杂度还是均摊 O(\alpha)）。

• 可以看出，这样构建出来的是一棵二叉树。

• 树上每个虚点对应的其实是一条边，故每个虚点其实对应着那条边的限制条件。

• 可以证明，自下而上的一条返祖路径上，限制是单调递增的。

• 于是可以在上面跑 dp/跑 dsu on tree/...，不过好像比较常见的还是求一下最远能走多远（倍增 lca 搞一下那样）。