数据结构与算法-进阶（八）AOV 网_aov网

摘要

AOV 网是图的一种类型，本质是一个有向无环图。AOV 网的排序被称为拓扑排序，它的实现思路是卡恩算法。代码实现上要留意删除顶点的操作，这是一个很巧妙的处理方式。

通常一项大的工程会被拆分为多个小的子工程。子工程之间可能存在一定的顺序关系，即一个子工程会在其他子工程完成之后才会开始。

在现代化管理中，人们通常用有向图来描述和分析一项工程的计划和实施过程，子工程被称为活动（Activity）。所以以顶点表示活动，有向边表示活动之间的先后关系，这样的图被称为 AOV 网（Activity On Vertex Network）。

AOV 网

标准的 AOV 网必须是一个有向无环图，即从任何一个顶点出发，无论怎么走，都无法回到这个顶点自身。如下图所示：

从图中可以梳理出每个顶点的依赖关系：

• B 依赖于 A；

• C 依赖于 B；

• D 依赖于 B；

• E 依赖于 B、C、D；

• F 依赖于 E。

拓扑排序

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

拓扑排序中有两个关键词，即前驱活动和后继活动，他们的定义分别是：

• 前驱活动：有向边起点的活动被称为终点的前驱活动，即只有当这个活动的前驱活动都完成之后，才可以开始该活动；

• 后继活动：有向边终点的活动被称为起点的后继活动。

如下图所示，它的拓扑排序是 A、B、C、D、E、F 或者 A、B、D、C、E、F（可以看出一个 AVO 网的拓扑排序不是唯一确定的）。

排序思路

拓扑排序的思路可以使用卡恩算法实现，它的大致逻辑是，假设一个存放排序结果的列表为 L，然后进行如下操作：

1. 把所有入度为 0 的顶点放到 L 中，并在图中删除该顶点；

2. 重复 1 步骤操作，直到图中没有度为 0 的 顶点为止。

然后可以比较 L 和图中总的顶点数量，如果 L 等于图中总的顶点数量，则拓扑排序完成，如果是小于的关系，那么就证明图中存在环，无法进行拓扑排序。

入度是什么？

一个顶点的入度为 x，是指有 x 条边以该顶点为终点；

代码实现

依据排序的思路，首先需要创建一个数组存放排序的结果。顶点入度的数量直接可以通过它的入度集合获取到。

关于删除顶点的操作，这里有一个取巧的点，就是创建一个 Map 存放入度不为 0 的顶点，和它的入度值。那么删除操作，就是将它的入度值减1处理。代码如下：

public List<V> topologiclSort() {
    List<V> list = new ArrayList<>();
    Queue<Vertex<V, E>> queue = new LinkedList<>();
    // 存放顶点和它的入度值
    Map<Vertex<V, E>, Integer> ins = new HashMap<>();
    vertices.forEach((v, vertex) -> {
        int size = vertex.inEdges.size();
        if (size == 0) {
            queue.offer(vertex);
        } else {
            ins.put(vertex, size);
        }
    });

    while (!queue.isEmpty()) {
        Vertex<V, E> vertex = queue.poll();
        list.add(vertex.value);

        for (Edge<V, E> edge : vertex.outEdges) {
            // 获取顶点的入度值，并 -1 达到删除顶点效果
            int toIn = ins.get(edge.to) - 1;
            if (toIn == 0) {
                queue.offer(edge.to);
            } else {
                ins.put(edge.to, toIn);
            }
        }
    }
    return list;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

总结

• AOV 网是一个有向无环图；

• 拓扑排序实现的思路可以使用卡恩算法处理，即不断获取入度为 0 的顶点；

• 删除顶点可以转换为保存顶点的入度值，将入度值在合适的地方减1操作。