最小生成树

_Cheems · 2023-08-07 21:05:03 · 个人记录

部分内容参考自网络。

基础概念

• 最小生成树的定义

  生成树：一个无向图 G 的生成树属于 G 的一个极小连通子图，包含该图的所有顶点 S，且只含 |S|-1 条边，也就是满足树的性质。

  最小生成树：边权和最小的生成树。

• 瓶颈生成树的定义

• 最小生成树的性质

  如有不严谨的地方，还请各位提出。

  1. 删去任意一条边后不再连通，加入任意一条边后出现环。

     这一点很重要，在修改最小生成树时有重要作用。

  2. 所有的边权和尽可能小（对于全图而言）。

  4. 最小生成树的树形不唯一，但边权和唯一。

  5. 最小生成树一定是瓶颈生成树，但瓶颈生成树不一定是最小生成树。

     对于前一条，考虑反证法：设最小生成树的最大边权为 w。若最小生成树不是瓶颈生成树，则瓶颈生成树的最大边权一定小于 w。那么只需删去 w，将瓶颈生成树中选取一条边加入最小生成树，使得删除后不连通的两部分连通，则可以得到一棵比原生成树更小的生成树。这与定义矛盾。

     运用这个性质，求瓶颈生成树时直接跑一遍最小生成树即可。

两种算法

• Prim

  • 简介

    时间复杂度为 O(n^2)，由于其需要搭配邻接矩阵适用，因此空间复杂度为 O(n^2)。

    本质上是贪心的思想，与 \operatorname{Dijkstra} 的连点法类似。

    将图分为两部分，一部分为生成树的点集 V，另一部分为非生成树的点集 S。

  • 算法流程

    定义 dis[u] 为 u 至 V 的最小距离。

    1. 初始化 dis 为无穷大，随便令一点的 dis 为 0。
    2. 每次从 S 中找到最小 dis 值 dis[id]，将 id 加入 V 中，同时将 ans 增加 dis[id]。
    3. 通过 id 更新 S 中点的 dis 值。
    4. 重复 1 ~ 3 步 n 次。
    5. 若在执行 2 时，发现找不到 id，则说明不存在最小生成树。否则输出 ans 即可。

  • 代码实现

    inline void prim(){
        dis[1]=0;
        for(int i=1; i<=n;++i){
            id=0;
            for(int j=1; j<=n;++j){
                if(!f[j]&&(!id||dis[j]<dis[id])){
                    id=j;
                }
            }
            if(dis[id]==0x3f3f3f3f){
                flag=1;
                return ;
            }
            f[id]=1;
            ans+=dis[id];
            for(int j=1; j<=n;++j){
                if(!f[j]){
                    dis[j]=min(dis[j],a[id][j]);
                }
            }
        }
    }

• Kruskal

  • 简介

    时间复杂度为 O(mlogm)，利用邻接表存边，空间复杂度为 O(m)（注意无向图要存两次）。

    将图视作若干个生成树（一个点也算）。每次合并都要使合并后得到的生成树尽可能小，那么最后便可得到最小生成树。

    因此从大到小对边进行排序，依次取边合并两端点，即可满足上述条件。

  • 算法流程

    1. 将边从大到小排序。
    2. 依次取边，若加入 e(u,v) 后不会产生环，则取 e(u,v) 作为最小生成树中的一条边，并将 ans 加上 w(u,v)。
    3. 若取不到 n-1 条边，则说明不存在最小生成树。否则输出 ans 即可。

  • 代码实现

    判断加入后是否产生环，考虑使用并查集解决。

    inline void kruskal(){
        sort(e+1,e+1+cnt,cmp);
        for(int i=1; i<=cnt;i++){
            int fu,fv,w;
            fu=find(e[i].u);
            fv=find(e[i].v);
            w=e[i].w;
            if(fu^fv){
                fa[fu]=fv;
                tot++;
                ans+=w;
            }
        }
    }