【算法】拓扑排序与最小生成树

封面画师：Nengoro(ネんごろぅ)     封面ID：68986081

本文参考视频：小马哥教育(SEEMYGO) 2019年 恋上数据结构与算法（第二季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化     Data Structure Visualizations

0. 前言

本文紧接 【高级数据结构之图】一文

本文紧接 【高级数据结构之图】一文

本文涉及的代码均在 【高级数据结构之图】一文中编写的代码基础上进行编写。

1. AOV 网

AOV网 —— Activity On Vertex Network

一项大的工程常被分为多个小的子工程：

• 子工程之间可能存在一定的先后顺序，即某些子工程必须在其他子工程完成后才能开始

在现代化管理中，人们常用有向图描述和分析一项工程的计划和实施过程，子工程被称为活动（Activity）：

• 以顶点表示活动、有向边表示活动之间的先后关系，这样的图简称为 AOV网 。

---

标准的AOV网必须是一个有向无环图（Directed Graph，简称 DAG）：

2. 拓扑排序

2.1 基本概念

前驱活动： 有向边起点的活动成为终点的前驱活动。只有当一个活动的前驱全部都完成后，这个活动才能进行。

后继活动： 有向边终点的活动成为起点的后继活动。

---

那什么是拓扑排序（Topological Sort）？

拓扑排序就是将 AOV 网中所有活动排成一个序列，使得每个活动的前驱活动都排在该活动前面。

比如上图的拓扑排序结果为 ： A、B、C、D、E、F 或者 A、B、D、C、E、F （结果不一定是唯一的）

2.2 实现思路

可以使用卡恩算法 （Kahn 于1962年提出）完成拓扑排序。

假设 L 是存放拓扑排序结果的列表：

①、把所有入度为 0 的顶点放入 L 中，然后把这些顶点从图中去掉

②、重复操作 ① ，直到找不到入度为 0 的顶点

如果此时 L 中的元素个数和顶点总数相同，说明拓扑排序完成。

如果此时 L 中的元素个数少于顶点总数，说明原图中存在环，无法进行拓扑排序。

注意： 进行拓扑排序的图都是有向无环图，即是一个标准的AOV网。

还有一点也需要注意，卡恩算法会将图中的顶点溢出，但实际情况是不允许删除的，因此还需要想另外的方式。

2.3 编码实现

在Graph接口中添加一个方法List<V> topologicalSort();，表示拓扑排序的方法，然后需要在ListGraph类中实现这个方法。

我们实现拓扑排序时不能像卡恩算法一样直接删除图中的顶点，需要想个办法进行代替。

需要创建一个动态数组，用于存储拓扑排序后的顶点，最后返回这个动态数组。

然后可以创建一个队列和映射，初始化时，将入度为 0 的顶点加入队列中，将入度不为 0 的顶点作为映射的Key，入度作为 Value 存入映射中。

初始化完毕后，从队列中移除一个顶点，将其放入动态数组中，然后遍历这个顶点出去的边，并计算这些边达到的顶点的入度减一后是否为 0 。如果为 0 ，将这些顶点加入队列中；如果不为 0 ，这些顶点的入度减一，存入映射中。重复这个操作，直到队列为空。

最终拓扑排序的代码如下：

@Override
public List<V> topologicalSort() {
    List<V> list = new ArrayList<>();
    Queue<Vertex<V, E>> queue = new LinkedList<>();
    Map<Vertex<V, E>, Integer> ins = new HashMap<>();
    // 初始化（将度为 0 的节点放入队列）
    vertices.forEach((V v, Vertex<V, E> vertex) -> {
        int in = vertex.inEdges.size();
        if (in == 0) {
            queue.offer(vertex);
        } else {
            ins.put(vertex, in);
        }
    });

    while (!queue.isEmpty()) {
        Vertex<V, E> vertex = queue.poll();
        // 放入返回结果中
        list.add(vertex.value);

        for (Edge<V, E> edge : vertex.outEdges) {
            int toIn = ins.get(edge.to) - 1;
            if (toIn == 0){
                queue.offer(edge.to);
            } else {
                ins.put(edge.to, toIn);
            }
        }
    }
    return list;
}

以上就是拓扑排序的代码，以经过初步测试，可放心 “食用”！😋

3. 生成树

3.1 基本概念

生成树（Spanning Tree），也称为支撑树。

连通图的极小连通子图，它含有图中全部的 n 个顶点，恰好只有 n - 1 条边。如：

3.2 最小生成树

基本概念

最小生成树（Minimum Spanning Tree，简称 MST），也称为最小权重生成树（Minimum Weight Spanning Tree）、最小支撑树，是所有生成树中权值最小的那棵。

最小生成树的概念适用于有权的连通图（无向）。

实际应用

最小生成树在许多领域都有重要的作用，例如：

要在 n 个城市之间铺设光缆，使它们都可以通信。铺设光缆的费用很高，且各个城市之间因为距离不同等因素，铺设光缆的费用也不同，如何使铺设光缆的总费用最低？这里就可以用到最小生成树。

如果图的每一条边的权值都互不相同，那么最小生成树将只有一个，否则可能会有多个最小生成树。

求最小生成树有两个经典的算法：

• Prim （普里姆算法）
• Kruskal （克鲁斯克尔算法）

3.3 Prim 算法

切分定理

切分（Cut）：把图中的节点分成两部分，称为一个切分。

比如下图中就有个切分 C = (S, T)，S = {A, B, D}，T = {C, E}

横切边（Crossing Edge）：如果一个边的两个顶点，分别属于切分的两部分，这个边成为横切边。

比如上图的边 BC、BE、DE 就是横切边。

切分定理： 给定任意切分，横切边中权值最小的边必然属于最小生成树。

Prim算法执行流程

假设 G = (V, E) 是有权的连通图（无向）， A 是 G 中最小生成树的边集

算法从 S = { u₀ } (u₀ ∈ V)，A = { } 开始，重复执行以下操作，到 S = V 为止

找到切分 C = (S, V - S) 的最小横切边 (u₀ , v₀ ) 并入集合 A ，同时将 v₀ 并入集合 S

执行过程图示：

3.4 Prim 的实现

父类的修改

在实现 Prim 算法之前，需要先在接口Graph中添加方法，假设命名为mst()，表示生成最小生成树。

然后一个问题就出来了，返回值是什么？

因为生成了最小生成树，返回值得是边信息（起点、终点和权值），那使用 Set 集合，比如Set<Vertex<V, E>>这样吗？

这样确实可以，但是这么做会暴露我们实现类的细节，不建议这么搞。

其实只需要在接口中创建一个表示边信息的内部类EdgeInfo就解决问题了。

除此之外，在求得最小生成树的时候还涉及到权值的比较，而在以后求最短路径的时候还会涉及到权值的相加，为了统一管理这两个地方，可以在将原本的接口修改为抽象类，然后添加一个接口WeightManager，用于管理那两个方法。

public abstract class Graph<V, E> {
    protected WeightManager<E> weightManager;

    public Graph() { }

    public Graph(WeightManager<E> weightManager) {
        this.weightManager = weightManager;
    }

    // 省略其他抽象方法
    ...
    
    // 最小生成树
    public abstract Set<EdgeInfo<V, E>> mst();
        
    public interface WeightManager<E> {
        int compare(E w1, E w2);
        E add(E w1, E w2);
    }

    public static class EdgeInfo<V, E> {
        private V from;
        private V to;
        private E weight;

        protected EdgeInfo(V from, V to, E weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public V getFrom() {return from;}

        public void setFrom(V from) {this.from = from;}

        public V getTo() {return to;}

        public void setTo(V to) {this.to = to;}

        public E getWeight() {return weight;}

        public void setWeight(E weight) {this.weight = weight;}

        @Override
        public String toString() {
            return "EdgeInfo{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }
}

其他修改

为了能够更好地实现 Prim算法，修改ListGraph中的Edge内部类，给这个内部类添加一个方法，以便可以简单地获取到边信息：

EdgeInfo<V, E> info() {
    return new EdgeInfo<>(from.value, to.value, weight);
}

除此之外，在获取最小生成树时，需要比较权值，我们选择添加比较器，因此ListGraph类需要增加一个成员变量和构造方法：

private Comparator<Edge<V, E>> edgeComparator = (Edge<V, E> e1, Edge<V, E> e2) -> {
    return weightManager.compare(e1.weight, e2.weight);
};

public ListGraph() { }

public ListGraph(WeightManager<E> weightManager) {
    super(weightManager);
}

这些都是为 Prim 算法的准备，接下来就是重头戏了。 👇

Prim 实现

先说说思路：

1、先获取图中的一个顶点（注意图不存在顶点的情况）

2、创建两个 HashSet，edgeInfos用于存储边信息，最后返回；addedVertices用于存储已经 “经过” 的顶点

3、将最开始获取的顶点加入到集合 addedVertices中

4、获取选择顶点的 outEdges 集合heap，并删除权值最小的那条边

5、将这条边存储到集合edgeInfos中，这条边到达的顶点存储到addedVertices中

6、获取上一步得到的边的所有 outEdges ，存入集合heap中，重复执行 456 三步，直到集合为空或edgeInfos的长度等于图顶点数减一（addedVertices的长度等于图中的顶点数）。

---

在思路分析中需要获取集合中权值最小的边，可以使用二叉堆来实现。在 JDK 中提供了优先级队列，优先级队列默认就是用最小堆实现的，也恰好满足我们的需要，但是不能同时根据集合和比较器创建一个优先级队列，当然也可以将集合中的元素一个一个添加到优先级队列中，但是为了效率，我们可以自己编写一个符合要求的最小堆（代码省略）。

最终 Prim 算法代码如下：

@Override
public Set<EdgeInfo<V, E>> mst() {
    return prim();
}

private Set<EdgeInfo<V, E>> prim() {
    Iterator<Vertex<V, E>> it = vertices.values().iterator();
    if (!it.hasNext()) return null;
    Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
    Set<Vertex<V, E>> addedVertices = new HashSet<>();
    Vertex<V, E> vertex = it.next();
    addedVertices.add(vertex);

    // 自己编写一个最小堆
    MinHeap<Edge<V, E>> heap = new MinHeap<>(vertex.outEdges, edgeComparator);
    // int edgeSize = vertices.size() - 1;
    int verticesSize = vertices.size(); // 少一个减一操作
    // 这里的循环着重理解
    while (!heap.isEmpty() && addedVertices.size() < verticesSize) {
        Edge<V, E> edge = heap.remove();
        if (addedVertices.contains(edge.to)) continue;
        edgeInfos.add(edge.info());
        addedVertices.add(edge.to);
        heap.addAll(edge.to.outEdges);
    }
    return edgeInfos;
}

以上就是 Prim 算法的代码，以经过初步测试，可放心 “食用”！😉

3.5 Kruskal 算法

执行过程： 按照边的权重顺序（从小到大）将边加入生成树中，直到生成树中含有 V - 1 条边（V 是顶点数量）。

需要注意的是： 若加入该边会与生成树形成环，则不加入该边。从第三条边开始，可能会与生成树形成环。

3.7 Kruskal 的实现

在实现 Kruskal 算法时，首选得判断图中没有顶点的情况。

然后将从所有边中依次选出权重最低的边，这里同样可以用到 最小堆 来实现，我们就采用实现 Prim 算法中的最小堆实现。

但是在依次选权重最低的边时需要注意会不会形成闭环的情况。如果是链表，判断有没有环可以使用快慢指针，而在这可以使用 并查集 。

并查集？并查集不是用来查找某个元素在哪个集合中的数据结构吗？怎么还能用来判断是否存在闭环呢？ 😕

其实很简单。求最小生成树时，最终需要返回边信息，在边信息中也隐藏了顶点信息。每一条边就隐藏了两个顶点（起始与终点），我们将最小生成树中边的顶点信息存入并查集中的一个集合里（在并查集中 union 这两个顶点），每次选择权值最小的边时，判断这条边的顶点信息是否存在同一个集合中。如果存在，表示会产生闭环，则放弃这条边，寻找下一条权值最小的边；如果不存在，就表示这条边是最小生成树中的边。

---

最终 Kruskal 算法代码如下：

@Override
public Set<EdgeInfo<V, E>> mst() {
    return kruskal();
}
private Set<EdgeInfo<V, E>> kruskal() {
    int edgeSize = vertices.size() - 1;
    // 图中没有顶点的时候
    if (edgeSize == -1) return null;
    Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
    MinHeap<Edge<V, E>> heap = new MinHeap<>(edges, edgeComparator);
    UnionFind<Vertex<V, E>> uf = new UnionFind<>();
    vertices.forEach((V v, Vertex<V, E> vertex) -> {
        uf.makeSet(vertex);
    });

    while (!heap.isEmpty() && edgeInfos.size() < edgeSize) {
        Edge<V, E> edge = heap.remove();
        // 判断选择的边是否构成环 可以使用并查集解决
        if (uf.isSame(edge.from, edge.to)) continue;
        edgeInfos.add(edge.info());
        uf.union(edge.from, edge.to);
    }
    return edgeInfos;
}

以上就是 Kruskal 算法的代码，以经过初步测试，可放心 “食用”！😄

3.8 复杂度对比

Kruskal 算法复杂度分析：

---

Prim 算法的复杂度会根据实现方式发生改变，如果没有选择最小堆实现，选择斐波那契堆实现，复杂度还可以再小一点。

我们实现的 Prim 算法采用了最小堆，但是最小堆的数据规模是变化的，数据规模逐渐增大，最坏情况下堆的规模是 E （边的数量）。这样的话，最坏情况下 Prim 算法的复杂度为 O(ElogE) 。

但我认为， Prim 算法相比于 Kruskal 算法会更优一点，因为 Prim 算法中堆的规模是逐渐增大的，而 Kruskal 算法中堆的规模一开始就是 E 。

---

在求得最小生成树的时候，Prim 算法采用了集合 HashSet 来存储最小生成树中的顶点，而 Kruskal 算法采用了并查集存储最小生成树的顶点，这两个算法为什么会有这个区别呢？

在 Prim 算法中放入集合 HashSet 中的顶点都是彼此相连的，可以存在于一个集合中。

Kruskal 算法中最小生成树的顶点往往不是连在一起的，而是分布于多个集合（这里的集合指数的聚集，并不是指集合 Set）中。如果使用集合 Set 来存储这些顶点，就需要多个集合 Set 来存储，而且 Kruskal 算法在运行过程中，还会将这些集合彼此合并或者判断是否有闭环生成，因此选择集合 Set 来存储这些数据就会变得异常麻烦，选择并查集来存储这些顶点就会完美地处理前面提到的问题。