Cancel

速通最小生成树（MST）

Algorithm

·

November 18, 2022

前言

介绍三种基本的最小生成树算法：

它们都是贪心算法

  1. 基于最小边的 Kruskal 算法
  2. 基于最小距离的点（到生成树）的 Prim 算法
  3. 基于连通分量最小出边的 Boruvka 算法

对于它们进行简单的比较

实现基于图论基础里面提到的数据结构

最小生成树的性质

介绍一下最小生成树的性质1，可能让我们对算法的理解能拨其冗繁、扼其要务，看得更清楚一些。

对于连通图 $G = (V, E)$ ，如果 $U$ 为它的非平凡子图（不是空集和它自身），则存在 $U$ 的所有出边（一头在 $U$，一头不在 $U$ ）中权值最小的边 $e$ 一定属于某棵 $G$ 上的最小生成树。

记 $T$ 为 $G$ 上的一棵最小生成树，

  1. 如果 $e$ 在 $T$ 上， 性质1成立；

  2. 如果 $e$ 不在 $T$ 上，由于 $T$ 是生成树，加入 $e$ 就会构成一个环（不妨标记这个环形路径为 $C$ ），并且一定存在C中$e$ 以外的一条 $U$ 的出边 $f$ ，由于 $e$ 是最小出边，那么 $f$ 一定权重大于等于 $e$ 。因此 $T-f+e$ 不仅是生成树，而且由于权重小于等于 $T$ , 是最小生成树。也就是 $e$ 属于一棵生成树，性质1仍然成立。

证毕。

直接推论

进一步地，如果出边 $e$ 是唯一最小，它一定属于所有最小生成树，反之如果是唯一最大，那一定不属于任何最小生成树。

子图 $U$ 上出边的性质也可适用于图上环状路径 $C$ 上的边。

生成性

如果 $U$ 属于 $G$ 上的某棵最小生成树，那么在加入一条最小出边后，仍然属于一棵最小生成树。

这样，可以从 $G$ 中任意一个点开始，按照诱导推理，不断地加最小出边，当图中每个点都被加入后，就得到了一棵最小生成树。

唯一性

如果 $G$ 上每条边的权重都是唯一的，那么最小生成树也是唯一的。

Kruskal 算法

大概读作 /’krʌs,gol/

描述

最简单的，基于最小出边的贪心算法

  1. 假设开始的时候每个点都是只包括自己的连通分量；
  2. 边按照权重排序，从最小边开始，若边上的两点不在同一连通分量里，就把它加入生成树，然后把两个点所在的连通分量连通为一个分量，最后就得到最小生成树；

实现

  1. 对边用堆或者提前排序维护从小到大的边的检查顺序；
  2. 用并查集维护连通分量
pub fn mst_kruskal(g: &Graph) -> Vec<(usize, usize)> {
    /* init sorted edge set */
    let mut sorted_edges = vec![];

    for (u, v, w) in g.edges() {
        sorted_edges.push((u, v, w));
    }

    sorted_edges.sort_unstable_by_key(|x| x.2);

    /* init disjoint set */
    let mut ds = UnionFind::new(Some(MergeBy::SZ));

    for v in g.vertexs() {
        ds.insert(v);
    }

    let mut res = vec![];

    for (u, v, _w) in sorted_edges {
        if ds.cfind(u) != ds.cfind(v) {
            ds.cunion(u, v);
            res.push((u, v));
        }
    }

    res
}

证明

Kruskal 算法完整的形式证明还是有点儿繁复的。

假设 $G$ 是加权连通图， $Y$ 是算法应用在 $G$ 上产生的子图

是生成树

  1. $Y$ 不存在环， 这是由算法加边时的检查所保证的；
  2. $Y$ 是连通的，因为所有边都被检查了一遍，只要两个点不在同一分量里就加入

且是最小生成树

首先提出一个假设 $P$：

​ 设 $F$（Forest）是算法在任意阶段生成的边集，则总有 $G$ 上的最小生成树包含 $F$ ，并且它（这棵生成树）里面的边之前阶段没有被算法拒绝过。

用归纳法证明 $P$ 成立：

  1. 在开始的时候，$F=\varnothing $ ，显然 $G$ 上任何最小生成树都包含 $F$ ，算法一开始也没有拒绝过任何边， $P$ 成立；

  2. 假设 $P$ 在算法的某个非最终阶段成立，将这时包含 $F$ 的最小生成树记为 $T$ ，下一个要加入的边记为 $e$ ：

    1. 如果 $e$ 在 $T$ 上， $P$ 成立；
    2. 如果 $e$ 不在 $T$ 上，由于 $T$ 是生成树，加入 $e$ 就会构成一个环（不妨标记这个环形路径为 $C$ ），而由于 $e$ 通过了算法检查，所以 $e$ 加入后，构不成 $F$ 上的环形结构，也就是说环形路径 $C$ 一定存在至少一条边不属于 $F$ 。不妨标记这样的一条边为 $f$ ，$f \neq e$。根据 $P$ 的定义， $T$ 上没有边之前被 $F$ 拒绝过， $f$ 如果不属于 $F$ ，则一定权重大于等于 $e$ 。因此 $T-f+e$ 不仅是生成树，而且由于权重小于等于 $T$ , 因此是最小生成树，而 $T-f+e$ 包含 $F+e$ ， $P$ 仍然成立。 因此我们证明了若 $P$ 在 $F$ 上成立，就有 $P$ 在 $F+e$ 上成立的递推关系。

归纳证毕，假设 $P$ 成立。

因此当 $F$ 是生成树的时候，一定有最小生成树包含它，也就是 $F$ 是最小生成树。

而之前我们已经证明了 $F$ 最终所生成的子图 $Y$ 是生成树， 于是有算法产生了一棵最小生成树，证毕。

时间复杂度

假设 $n=\vert V \vert$，$m=\vert E \vert$

复杂度等于边排序 $O(m \log m)$ + 并查集操作 $O(m \log n)$ ，等于 $O(m (\log m + \log n))$ 。

Prime 算法

形式上类似 Dijkstra 算法，通过追踪距既有生成树最短距离的点（通过在堆上不断“Relax”的方式）来寻找最小出边。

描述

  1. 选取图中任意一点开始，作为生成树的根节点，把其余点到生成树的最短距离初始化为 $+\infty$ ，根节点的生成树最短距离初始化为 $0$ ，初始化每个点 $u$ 到生成树的最短边的对应点 $\texttt{pair}(u)$ 为 None ，记录 $\texttt{pair}$ 的作用是为了方便以边的形式输出最小生成树；
  2. 把所有点加入剩余点集 $R$；
  3. 每次从 R 中取出到生成树距离最小的点记为 $u$ ，把边 $(u, \texttt{pair}(u))$ 加入边集 $E$ 中。检查它的邻居中不在生成树上的点 $v$ ，如果边的权重 $w_{\large uv}$ ，与生成树最短距离 $\texttt{dis}(v)$ ，有 $w_{\large uv} < \texttt{dis}(v) $ ，更新 $\texttt{dis}(v)$ 为 $w_{\large uv}$ ，也更新 $\texttt{pair}(u)$ 为 $u$ ；
  4. 当 $R = \varnothing$ 时，退出，得到的 $E$ 即为一棵最小生成树

实现

关键显然在于维护生成树距离的堆的选择，这涉及两个堆操作 pop 和 decrease-key ，经典地使用 Fib 堆 一文中介绍过），或者更好的替代：多叉堆 。

pub fn mst_prim(g: &Graph) -> Vec<(usize, usize)> {
    let mut res = vec![];

    /* choose an arbitray node as root */

    let mut viter = g.vertexs();
    let root;

    if let Some(_root) = viter.next() {
        root = _root;
    } else {
        return res;
    }

    /* setup rest collection */

    let mut rest: HashSet<usize> = HashSet::new();

    /* init dis heap && dis edge map */

    let mut dis = FibHeap::new();

    let mut dis_edge = HashMap::new();

    dis.push(root, 0);
    dis_edge.insert(root, Some(root));

    for v in viter {
        rest.insert(v);
        dis.push(v, isize::MAX);
        dis_edge.insert(v, None);
    }

    while !rest.is_empty() {
        // u is current vertex
        let (u, _uw) = dis.pop_item().unwrap().clone();

        // "decrease-key" (It's increase-key actually for min-heap)
        rest.remove(&u);

        let u_pair = get!(dis_edge => u).unwrap();

        if u_pair != u {
            res.push((u, u_pair));
        }

        // calc adj

        let adjs = get!(g.e => u);

        /* update dis heap */
        for v in adjs.into_iter().filter(|v| rest.contains(v)) {
            let w_uv: isize = get!(g.w => (u, v));

            if w_uv < *get!(dis => v) {
                dis.decrease_key(v, w_uv);
                dis_edge.insert(v, Some(u));
            }
        }
    }

    res
}

证明

根据最小生成树的生成性质，同上，略。

时间复杂度

经典使用斐波那契堆： $O(\text{log}n) + O(m) = O(\text{log}n + m)$

使用大基数的 $k$ 叉堆： $O(1) + O(m) = O(m)$

Boruvka 算法

Borůvka (捷克语) ，大概读作 /,bros’gɑʊl/

描述

对每个连通分量加最小出边，直到没有出边为止。

可以算作对 Kruskal 算法的改进，因为实际上 Kruskal 算法对所有边排序是有点儿浪费比较次数了。

  1. 开始的时候，图中每个点都是一个连通分量，对所有边遍历，选取其中跨两个连通分量的边，用它更新两个连通分量在这一轮迭代里的最小出边；
  2. 一轮结束后，把新选取的最小出边加入结果集，并连接两个分量，直到没有任何跨两个连通分量的边。

注意：

  1. 显然作为一个优化，加入结果集的边就不需要再遍历了
  2. 具体的算法实现中，注意不要让权重相等的边导致结果中出现环

实现

pub fn mst_boruvka(g: &Graph) -> Vec<(usize, usize)> {
    let mut res = HashSet::new();

    // using lexicograph order
    let mut dsu = UnionFind::new(Some(MergeBy::SZ));

    for v in g.vertexs() {
        dsu.insert(v);
    }

    // components cheapest edges: (weight, usize)
    let mut cand_edges: HashSet<(usize, usize, isize)> = g.edges().collect();

    loop {
        let mut comp_min_edges: HashMap<usize, Option<(isize, usize, usize)>> =
            HashMap::new();

        for (u, v, w) in cand_edges.iter().cloned() {
            let pu = dsu.cfind(u);
            let pv = dsu.cfind(v);

            if pu == pv {
                continue;
            }

            let pu_min_edge = comp_min_edges
                .get(&pu)
                .cloned()
                .unwrap_or(None);

            if pu_min_edge.is_none() || Some((w, u, v)) < pu_min_edge {
                comp_min_edges.insert(pu, Some((w, u, v)));
            }

            let pv_min_edge = comp_min_edges
                .get(&pv)
                .cloned()
                .unwrap_or(None);

            if pv_min_edge.is_none() || Some((w, u, v)) < pv_min_edge {
                comp_min_edges.insert(pv, Some((w, u, v)));
            }
        }

        let mut continue_flag = false;

        for (_, opt) in comp_min_edges.into_iter() {
            if let Some((w, u, v)) = opt {
                res.insert((u, v));
                dsu.cunion(u, v);
                cand_edges.remove(&(u, v, w));

                continue_flag = true;
            }
        }

        if !continue_flag {
            break;
        }
    }

    res.into_iter().collect()
}

利用属性的简单证明

开始时 $G$ 中每个点都是一个连通分量，每次选取最小出边，连接两个分量。首先这两个分量分别属于某棵最小生成树，其中任一个分量加上出边仍然是最小生成树的一部分，显然 （也许并没有显然）应当是这两个连通分量合起来仍然属于某棵最小生成树。

完整证明

完整证明过于复杂，另行查阅资料，不介绍。

时间复杂度

由于每次迭代后连通分量至少减半（每个新分量都没再连通过），所以最外层迭代次数是 $O(\log n)$，每次边的遍历是 $O(m)$ ，并查询是 $O(\text{log}n)$ ，所以时间复杂度为 $O(m\log n\log n)$ 。

时间复杂度简单比较

时间复杂度涉及 $n$ 和 $m$，按照图的稀疏度分两个维度讨论（对于连通图，$m\geqslant n-1$ ）


对于稀疏图，$m=n$ :

Kruskal: $O(m(\text{log}m+\text{log}n)) = O(n\text{log}n)$

Prime: $O(\text{log}n+m) = O(n+\text{log}n) = O(n)$

Boruvka: $O(m\text{log}n\text{log}n) = O(n\text{log}n\text{log}n)$

复杂度从优到劣， Prim > Kruskal > Boruvka


对于稠密图，$m=n^2$

Kruskal: $O(m(\text{log}m+\text{log}n)) = O(n^2\text{log}n\text{log}n)$

Prime: $O(\text{log}n+m) = O(n^2 + \text{log}n)$

Boruvka: $O(m\text{log}n\text{log}n) = O(n^2\text{log}n\text{log}n)$

复杂度从优到劣， Prim > Kruskal = Boruvka


好像仅从复杂度上，经典实现里 Prim都是各方最优。

从优化实现上，Prim 的优化和 Boruvka 算法的拓展都可以到 $O(m)$ 。

后续

基于 Boruvka 的线性算法2 复杂的部分在于一个去重（zhong）边的最小生成树的验证算法（原始提出和 Targan 最近共同祖先同一篇论文里），没有具体实现的介绍，只有原始的算法的论文，大体看了以下，应该可以弄明白，但是要花不少时间，有点儿鸡肋，就这样吧。

引用

  1. https://en.wikipedia.org/wiki/Minimum_spanning_tree ↩

  2. https://en.wikipedia.org/wiki/Expected_linear_time_MST_algorithm ↩

© minghu6

·

theme

Simplex theme logo

by golas