9.拓扑排序（Topological Sort）

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

拓扑排序
**
前驱活动： 有向边起点的活动称为终点的前驱活动
只有当一个活动的前驱全部完成后，这个活动才能进行

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

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

卡恩算法（Kahn于1962年提出）

假设L是存放拓扑排序结果的列表
1.把所有入度为0的顶点放入L中，然后把这些顶点从图中去掉
2.重复操作 1 ，直到找不到入度为0的顶点
如果此时L中的元素个数和顶点总数相同，说明拓扑排序完成
如果此时L中的元素个数少于顶点总数，说明原图中存在环，无法进行拓扑排序

@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) -> {
            if (vertex.inEdges.size() == 0) {
                queue.offer(vertex);
            }else {
                ins.put(vertex, vertex.inEdges.size());
            }
        });
        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;
    }