拓扑排序

摘自https://blog.csdn.net/qq_37618797/article/details/81070577

定义：

把AOV网（用定点表示活动，用弧表示活动间优先关系的有向图）络中各个顶点按照它们互相之间的优先关系排列成一个线性序列的过程叫做拓扑排序。

方法：

在有向图中选一个没有前驱的顶点并且输出
从图中删除该顶点和所有以它为尾的弧，即删除所有与它有关的边。
重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。

例题：

首先我们找到无前驱顶点C1和C9，我们删除掉C1，输出C1，并删除所有与C1相连的边

接着再从C2，C4，C9这三个无前驱顶点中选择一个删除掉，我们删除C2，输出C2，并删除所有与C2相连的边

最终得拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8。

注意：拓扑序列并不唯一，C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8 也是一种拓扑序列。

关键代码

public void topoSort() throws Exception{
        int count = 0;//判断是否所有的顶点都出队了,若有顶点未入队(组成环的顶点)，则这些顶点肯定不会出队
        
        Queue<Vertex> queue = new LinkedList<>();// 拓扑排序中用到的栈,也可用队列.
        //扫描所有的顶点,将入度为0的顶点入队列
        Collection<Vertex> vertexs = directedGraph.values();
        for (Vertex vertex : vertexs)
            if(vertex.inDegree == 0)
                queue.offer(vertex);
        //度为0的顶点出队列并且更新它的邻接点的入度
        while(!queue.isEmpty()){
            Vertex v = queue.poll();
            System.out.print(v.vertexLabel + " ");//输出拓扑排序的顺序
            count++;
            for (Edge e : v.adjEdges) 
                if(--e.endVertex.inDegree == 0)
                    queue.offer(e.endVertex);
        }
        if(count != directedGraph.size())
            throw new Exception("Graph has circle");
    }

输出：

拓扑序列：1 2 3 4 5 7 9 10 11 12 6 8