拓扑排序(Topological Order)是指，将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。

这样说，可能理解起来比较抽象。下面通过简单的例子进行说明！
例如，一个项目包括A、B、C、D四个子部分来完成，并且A依赖于B和D，C依赖于D。现在要制定一个计划，写出A、B、C、D的执行顺序。这时，就可以利用到拓扑排序，它就是用来确定事物发生的顺序的。

在拓扑排序中，如果存在一条从顶点A到顶点B的路径，那么在排序结果中B出现在A的后面。

拓扑排序步骤

1. 构造拓扑排序的结果队列T(topological)；
2. 计算所有顶点的入度；
3. 如果存在入度为零且没有排序过的顶点，则
   3.1 将入度为0的顶点放入队列T,
   3.2 去掉以这些顶点为起点的边,
   3.3 标记这些顶点已经被排序过,
   3.4 返回步骤2，重新计算剩余定点入度
4. 若果未排序的顶点入度都不为零，说明剩余的顶点组成了环，返回-1

Java实现

邻接矩阵图数据结构实现

承接前文的MatrixDG数据结构：

    //拓扑排序，如果无环，输出排序队列，返回1，若果有环，返回-1    public int topoSort(){        //设置是否访问过标记，初始化都是false        boolean[] visited=new boolean[size];        for(int i=0;i<size;i++){            visited[i]=false;        }        //拓扑排序结果存储队列        LinkedList<Integer> topo=new LinkedList<Integer>();        //调用拓扑排序算法        int result=topoSort(visited,topo);        //输出拓扑排序结果        if(result==1){            for(int i=0;i<topo.size();i++){                System.out.println(vertexs[topo.get(i)]+" ");            }        }        return result;    }    public int topoSort(boolean[] visited,LinkedList<Integer> topo){        //1，计算每个顶点的入度        int[] inDegree=new int[size];        for(int i=0;i<size;i++){            inDegree[i]=0;            for(int j=0;j<size;j++){                if(matrix[j][i]!=0&&visited[j]==false){                    inDegree[i]++;                }            }        }        //2，是否有环标记        boolean hasCircle=true;        for(int i=0;i<size;i++){            if(inDegree[i]==0&&visited[i]==false){//如果一个顶点入度为零且未被排序，则需要加入到队列中，且说明还没有发现环                hasCircle=false;                topo.add(i);//加入到队列中//                System.out.println(vertexs[i]);                visited[i]=true;//标记该顶点已被访问过            }                        }        if(hasCircle){//如果不存在还未被排序且入度为零的点，说明剩余的顶点构成了环，返回-1            System.out.println("Has Circle");            return -1;        }        //3,如果还可以继续进行排序，检验是否已全部排序过,通过已排序的顶点数量可以判断        if(size!=topo.size()){            return topoSort(visited,topo);        }else{            return 1; //如果都排序过了返回1        }    }

邻接表图数据结构实现

承接前文的ListDG数据结构：

    //拓扑排序，如果无环，输出排序队列，返回1，若果有环，返回-1    public int topoSort(){        //设置是否访问过标记，初始化都是false        boolean[] visited=new boolean[size];        for(int i=0;i<size;i++){            visited[i]=false;        }        //拓扑排序结果存储队列        LinkedList<Vertex> topo=new LinkedList<Vertex>();        //调用拓扑排序算法        int result=topoSort(visited,topo);        //输出拓扑排序结果        if(result==1){            for(int i=0;i<topo.size();i++){                System.out.println(topo.get(i).ch);            }        }        return result;    }    private int topoSort(boolean[] visited,LinkedList<Vertex> topo){        //1，计算每个顶点的入度        int[] inDegree=new int[size];        for(int i=0;i<size;i++){            Vertex node=vertexLists[i];            while(node!=null){                if(visited[i]==false){                    inDegree[getPosition(node.ch)]++;                }                node=node.next;            }            inDegree[i]--;//头节点不算所以减去1        }        //2，是否有环标记        boolean hasCircle=true;        for(int i=0;i<size;i++){            if(inDegree[i]==0&&visited[i]==false){//如果一个顶点入度为零且未被排序，则需要加入到队列中，且说明还没有发现环                hasCircle=false;                topo.add(vertexLists[i]);//加入到队列中//                System.out.println(vertexs[i]);                visited[i]=true;//标记该顶点已被访问过            }                        }        if(hasCircle){//如果不存在还未被排序且入度为零的点，说明剩余的顶点构成了环，返回-1            System.out.println("Has Circle");            return -1;        }        //3,如果还可以继续进行排序，检验是否已全部排序过,通过已排序的顶点数量可以判断        if(size!=topo.size()){            return topoSort(visited,topo);        }else{            return 1; //如果都排序过了返回1        }    }