最小生成树

最小生成树介绍

最小生成树

在介绍最小生成树前,先介绍一下生成树:在一张联通无向图中,我们取图上的所有点,并取最少的边将其相连使其连通生成一棵树,这个树就被称作这张图的生成树。因为树的边数一定是点数-1,所以就是取 \(n-1\) 条边来连通 \(n\) 个点。

那么最小生成树(Minimum Spanning Tree),是最小权重生成树的简称。规定树的权值为树上所有边的权值和,那么它就是一张连通加权无向图中一颗权值最小的生成树,如上图。由定义可以看出,最小生成树不一定唯一


对于如何生成最小生成树的问题,我们有两种常见的解决方法,分别是Prim算法和Kruskal算法,两者都基于贪心。

Prim算法

给定图 \(G(V, E)\) ,我们逐步进行Prim算法,假设在过程中,\(V_{new}\) 表示已经选中作为生成树上的结点,\(E_{new}\) 表示已经选中作为最小生成树上的边。

规定Prim算法如下:

  1. 初始化一个结点 \(x\) 加入 \(V_{new}\) ,则 \(V_{new} = {x}\) 。由于最小生成树包含所有节点,我们可以用任意一个结点初始化。
  2. 从集合 \(E\) 中选择权值最小的边 \((u, v)\) ,满足 \(u \in V_{new}\) 且 \(v \notin V_{new}\) ,将 \(v\) 加入集合 \(V_{new}\) 中,把 \((u, v)\) 加入 \(E_{new}\) 中。
  3. 重复操作,直到所有点都已经被选中加入最小生成树中,即 \(V_{new} = V\) 。
  4. 根据 \(V_{new}\) 和 \(E_{new}\) 所得到的新图 \(G_{new}(V_{new}, E_{new})\) 即为原图 \(G(V, E)\) 的最小生成树。

只需要证明根据第二步所得到边一定为最优解即可。

  1. 按照Prim算法得到的第一条边一定是最小生成树上的边。

    如果不是,我们把这一条边加入到最小生成树中,形成回路,我们让最小的边取代回路中比它大的边,得到权值更小的生成树。所以第一条边一定是最小生成树上的边。

  2. 假设在某一个步骤中,Prim得到的点集为 \(V_{new} = \{v1, v2, v3 \ldots vs-1\}\) 。 根据Prim算法,我们应该选择与这些点有交集的边中,权值最小的边。

    假设这个权值最小的边连接 \(V_{new}\) 中的 \(vk\) ,如果不选择这条边,那么我们把这条边加入最小生成树中,形成一个回路,且这个回路包含 \(vk\) ,我们假设连接 \(vk\) 的那条边另一端为 \(vi\) ,我们用权值最小的边替换掉 \((vk, vi)\) ,得到的生成树权值一定不大于最小生成树,因此选择这条边为最优边。

int h[N], e[M], w[M], ne[M], idx; // 邻接表存图
bool st[N]; // st(x) 表示x点已经加入生成树中
int dist[N]; // dist(x) 表示x点距离已经生成的树的最小距离

int prim () // 返回最小生成树的权值
{
    int ret = 0;
    memset(d, 0x3f, sizeof d); d[1] = 0; // 初始化从1开始,最开始生成树上的V和E都为空
    for (int i = 0; i < n; i ++ ) // 要加入n个点,迭代n次,每次放进一个点
    {
        // 找出距离当前生成树最近的点
        int t = -1;
        for (int k = 1; k <= n; k ++ )
            if (!st[k] && (t == -1 || dist[k] < dist[t])) t = k;
        
        // 把选择的点加入生成树中
        st[t] = true;
        ret += dist[t];
        
        // 由于加入了一个点,那么其他点也可以通过连接这个点到达生成树,更新dist
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            dist[j] = min(dist[j], w[i]);
        }
    }
    return ret; // 返回最小生成树的权值
}

有没有觉得Prim算法和Dijkstra算法雷同?没错,它们都是根据同样的贪心思想,唯一的区别仅仅在于更新的时候。

Prim算法复杂度:根据上述代码,复杂度为 \(O(n^2 + 2E)\) ,由于图上每个点至多被更新 \(1\) 次,所以图的所有边至多被更新 \(2\) 次。

与Dijsktra算法一样,Prim算法可以使用二叉堆优化,复杂度降到 \(O((n + 2E)logn)\) 。


Kruskal 算法

如果说Prim算法是小树长成大树的过程,那么Kruskal算法就是拼图的过程。

Prim算法基于点来扩大树,而Kruskal基于边来扩大,具体来说,该算法的过程如下:

  1. 将图 \(G(V, E)\) 的所有边按权值进行非递减排序。
  2. 初始化每个点都为单独的连通分量。(因为此时我们还没有选择边作为最小生成树的一部分)
  3. 从后往前检查所有边\((u, v)\) 。
    • \(u\) 和 \(v\) 在同一个连通分量里,那么加入 \((u, v)\) 会产生环,因此不能选择。
    • \(u\) 和 \(v\) 不在一个连通分量里,那么加入 \((u, v)\) 一定是最优的。如果不加入,形成生成树 \(T\) ,把 \((u, v)\) 加入 \(T\) 中,会形成环,环中包含 \((u, v)\) 和另外一条权值不小于 \((u, v)\) 的边,我们把这条边用 \((u, v)\) 替换,不会使结果变差,因此 \((u, v)\) 是最优的选择。

因为会考虑所有边,因此一定能构成一颗完整的最小生成树(除非原图不连通)。

在Kruskal算法中,最关键的地方在于“连通”分量的查询和合并,需要知道两个点是否在一个连通分量中,以及如果不是在一个连通分量,需要将其合并,我们可以使用并查集来支持此操作。

struct Edge {
    int u, v, d; // 表示边两端的点以及边权
    bool operator < (const Edge & rhs) const { // 重载小于号,支持比较
        return d < rhs.d;
    }
}

int p[N];
Edge edges[M];
int n, m;

int find (int x) { return p[x] == x ? x : p[x] = find(p[x]); }

int kruskal ()
{
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    sort(edges + 1, edges + m + 1); // 假设边集从1开始存储
    
    int ret = 0, cnt = 0; // cnt表示目前已经选择了多少条边(生成树只需要n-1条边)
    for (int i = 1; i <= m && cnt < n - 1; i ++ )
    {
        int u = edges[i].u, v = edges[i].v, d = edges[i].d;
        u = find(u), v = find(v);
        if (u == v) continue;
        ++ cnt, res += d, p[u] = v;
    }
    
    if (cnt != n - 1) return -1; // 原图不连通,没有生成树,何谈最小
    return ret;
}
上一篇:Prim算法解决最小生成树 (解决修路问题)


下一篇:Git 分支管理