引言

工程中尝尝氛围很多步骤完成，有些步骤可以同步进行，而有些步骤需要某些步骤完成后才能进行，如何安排它们的流程是项目实施要考虑的重要问题，这就是拓扑排序问题。拓扑排序，它可以决定哪些子工程必须要先执行，哪些子工程要在某些工程执行后才可以执行。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。
一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行（对于数据流来说就是死循环）。在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。

拓扑排序思想

1.在有向图中选一个没有前驱的顶点并且输出;
2.从图中删除该顶点和所有以它为尾的弧（白话就是：删除所有和它有关的边）;
3.重复上述两步，直至所有顶点输出，或者当前图中不存在无前驱的顶点为止，后者代表我们的有向图是有环的，因此，也可以通过拓扑排序来判断一个图是否有环。
拓扑排序有点像抽丝剥茧，每一次遍历都会去掉最外层的"壳"，抽完为止。
图解
1.针对下图:

有入度0的顶点V1和V6,先把他们放入集合S=[V1,V6]，这里随机取出V6遍历,S=[V1]。
2.V6遍历完，去掉和V4、V5的边(入度减1)，图结构如下:

3.从集合中取出V1,删除边，V2、V3、V4入度减一后,V4和V3入度为0，S=[V3,V4],图结构如下:

4.从集合中取出V4或者V3(取哪一个看具体算法),这里取V4,V5入度为减一不为0,S为[V3],图结构为:

5,从集合中取出V3，V2、V5入度为0，S=[V2,V5]，图结构如下:
image
6.继续输出集合中蒸鱼顶点，最后的该图的一个拓扑排序结果为:

v6—>v1—>v4—>v3—>v5—>v2。
注意:拓扑排序仅反应顶点间的层序关系，输出结果不唯一。

代码实现

代码实现，我们引入一个集合(栈或者队列均可)，存放未遍历的入度为0的顶点;引入计数变量检测图是否遍历完。具体实现如下:

package graphic;

import queue.Queue;

/**
 * Created by chenming on 2018/6/16
 * 拓扑排序
 */
public class TopologySort {
    private class VNode {
        int value;//值
        int inDegree;//入度
    }

    private int[][] map;//邻接矩阵
    private VNode[] nodes;

    public TopologySort(int[][] map) {
        this.map = map;
        nodes = new VNode[map.length];
        for (int i = 0; i < map.length; i++) {
            //初始化入度
            VNode node = new VNode();
            node.value = i;
            node.inDegree = getIndegree(i);
            nodes[i] = node;
        }
    }

    /**
     * 从邻接矩阵中得到顶点入度
     *
     * @param index
     * @return
     */
    private int getIndegree(int index) {
        int in = 0;
        for (int i = 0; i < map.length; i++) {
            if (0 < map[i][index] && map[i][index] < Integer.MAX_VALUE) {
                in++;
            }
        }
        return in;
    }

    /**
     * 有向图的拓扑排序,，思路如下:
     * 1,类似广度优先遍历,引入队列保存入度为0的未遍历节点
     * 2.每去掉一个顶点，则去掉该顶点的边，即它所有邻接顶点的顶点入度-1，如果为0则加入队列
     * 3.循环执行步骤2，直到队列为空
     * 4.循环结束检测是否遍历完整，如果没有遍历完全，则表示有回环
     */
    public void topologySort() {
        Queue<Integer> queue = new Queue<>();//保存入度为0的索引
        int numb = map.length;
        int count = 0;//校验用
        //收集入度为0的顶点
        for (int i = 0; i < numb; i++) {
            if (nodes[i].inDegree == 0) {
                queue.enquene(i);
            }
        }

        while (!queue.isEmpty()) {
            int index = queue.dequeue();
            System.out.println("拓扑排序:" + index);
            count++;
            //遍历完"删除"顶点index的所有边,即减少它邻接顶点的入度
            for (int i = 0; i < numb; i++){
                if(map[index][i] > 0 && map[index][i] < Integer.MAX_VALUE){
                    if(--nodes[i].inDegree == 0){
                        //入度减一后，加入队列
                        queue.enquene(i);
                    }

                }
            }

        }

        if(count != numb){
            throw new RuntimeException("图中存在回环");
        }

    }
}

测试图用例:

拓扑排序用例.png

测试代码:

   @Test
    public void testTopol() {
        int INF = Integer.MAX_VALUE;
        int[][] map = {
                {0, INF, INF, INF, 1, 1, INF, INF, INF, INF, INF, 1, INF, INF},//0
                {INF, 0, 1, INF, 1, INF, INF, INF, 1, INF, INF, INF, INF, INF},//1
                {INF, INF, 0, INF, INF, 1, 1, INF, INF, 1, INF, INF, INF, INF},//2
                {INF, INF, 1, 0, INF, INF, INF, INF, INF, INF, INF, INF, INF, 1},//3
                {INF, INF, INF, INF, 0, INF, INF, 1, INF, INF, INF, INF, INF, INF},//4
                {INF, INF, INF, INF, INF, 0, INF, INF, 1, INF, INF, INF, 1, INF},//5
                {INF, INF, INF, INF, INF, 1, 0, INF, INF, INF, INF, INF, INF, INF},//6
                {INF, INF, INF, INF, INF, INF, INF, 0, INF, INF, INF, INF, INF, INF},//7
                {INF, INF, INF, INF, INF, INF, INF, 1, 0, INF, INF, INF, INF, INF},//8
                {INF, INF, INF, INF, INF, INF, INF, INF, INF, 0, 1, 1, INF, INF},//9
                {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 0, INF, INF, 1},//10
                {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 0, INF, INF},//11
                {INF, INF, INF, INF, INF, INF, INF, INF, INF, 1, INF, INF, 0, INF},//12
                {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 0},//13
        };
        TopologySort ts = new TopologySort(map);
        ts.topologySort();
    }

输出:

拓扑排序:0
拓扑排序:1
拓扑排序:3
拓扑排序:4
拓扑排序:2
拓扑排序:6
拓扑排序:5
拓扑排序:8
拓扑排序:12
拓扑排序:7
拓扑排序:9
拓扑排序:10
拓扑排序:11
拓扑排序:13

完整代码地址:数据结构与算法学习JAVA描述GayHub地址