graph-topological-sort

摘要：AOV简介，拓扑排序的思路及实现

AOV网（Activity On Vertex Network）

在一个表示工程的有向图中，用顶点表示活动（Activity），用有向边表示活动之间的先后顺序，AOV网中不能出现环。

拓扑排序

拓扑排序是对有向无环图的顶点的一种排序，使得如果存在一条从vi到vj的路径，那么排序中vj就出现在vi的后面

思路：

• 从任意一个入度为0的顶点开始，将这个顶点及从这个顶点出发的边删除
• 重复上述操作，直到找不到入度为0的顶点

public List<K> topologicalSort() {
    List<K> list = new ArrayList<>();

    Queue<Vertex<K, E>> zeroInDegreeQueue = new LinkedList<>();
    Map<Vertex<K, E>, Integer> inMap = new HashMap<>();
    vertices.forEach((k, v) -> {
        if (v.inEdges.size() == 0) {
            zeroInDegreeQueue.offer(v);
        } else {
            inMap.put(v, v.inEdges.size());
        }
    });

    while (!zeroInDegreeQueue.isEmpty()) {
        Vertex<K, E> vertex = zeroInDegreeQueue.poll();
        list.add(vertex.key);
        vertex.outEdges.forEach(edge -> {
            inMap.put(edge.to, inMap.get(edge.to) - 1);
            if (inMap.get(edge.to) == 0) {
                zeroInDegreeQueue.offer(edge.to);
            }
        });
    }
    return list;
}