如果图中存在环(回路)，那么该图不存在拓扑排序，在这里我们讨论的都是无环的有向图。
什么是拓扑排序
一个例子
对于一部电影的制作过程，我们可以看成是一个项目工程。所有的工程都可以分为若干个"活动"的自工程。在这些活动之间，通常会受到一定的条件约束，如其中某些活动必须在另一些活动完成之后才能开始。比如，电影制作不可能在人员到位进驻场地时，导演还没有找到，也不可能在拍摄过程中，场地都没有。这些听起来就很荒谬。
在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，称为AOV网(Activity On Vertex Network)。
AOV网中的弧表示活动之间存在的某种制约关系。
那么拓扑排序，其实就是对一个有向图构造拓扑序列的过程。构造时有两个结果：
- 如果此网的全部顶点都被输出，说明该网是不存在环的AOV网
- 如果输出的顶点数少了，说明这个网存在环，不是一个AOV网
算法思路
从AOV网中选择一个入度为0的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧。继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。
算法实现
数据结构
由于拓扑排序中，需要删除顶点，那么采用邻接矩阵的方式就不太合适，我们可以使用邻接表，这样会更方便。
在算法运行过程中，始终要查找入度为0的顶点，我们在原来顶点表结构的基础上，增加一个入度域in，表示该顶点入度的数字。
边表节点结构体：
public class EdgeNode {
int adjevex;
int weight;
EdgeNode next;
public EdgeNode(int adjevex, EdgeNode next) {
this.adjevex = adjevex;
this.next = next;
}
}
顶点表节点结构体：
public class VertexNode {
int in;
Object data;
EdgeNode firstedge;
public VertexNode(Object data, int in, EdgeNode firstedge) {
this.data = data;
this.in = in;
this.firstedge = firstedge;
}
}
示例AOV图：
对应的邻接表为：
在算法中，我们还需要使用到一个栈，用来存储处理过程中入度为0的顶点下标，目的是为了避免每次查找时都需要遍历顶点表找有没有入度为0的顶点。
拓扑算法代码实现：
package 拓扑排序;
import java.util.Stack;
public class TopologySort {
static VertexNode[] adjList;
Stack stack = new Stack();
public String ToplogicalSort() {
EdgeNode e;
int k, gettop;
int count = 0;
for (int i = 0; i < adjList.length; i++) {
if(adjList[i].in == 0) {
stack.push(i);
}
}
while(!stack.empty()) {
gettop = (int) stack.pop();
System.out.print(adjList[gettop].data + "->");
count++;
for (e = adjList[gettop].firstedge; e != null; e = e.next) {
k = e.adjevex;
if((--adjList[k].in) == 0) { //将其入度减少一位，目的是将顶点上的弧删除
stack.push(k);
}
}
}
System.out.println();
return count < adjList.length ? (String) "ERROR" : (String) "OK";
}
public static EdgeNode getAdjvex(VertexNode node) {
EdgeNode e = node.firstedge;
while(e != null) {
if(e.next == null) break;
else
e = e.next;
}
return e;
}
public static void main(String[] args) {
int[] ins = {0, 0, 2, 0, 2,3,1,2,2,1,1,2,1,2};
int[][] adjvexs = {
{11, 5, 4},
{8,4,2},
{9, 6, 5},
{13, 2},
{7},
{12, 8},
{5},
{},
{7},
{11, 10},
{13},
{},
{9},
{}
};
adjList = new VertexNode[ins.length];
for (int i = 0; i < ins.length; i++) {
adjList[i] = new VertexNode("V"+i, ins[i],null);
if(adjvexs[i].length > 0) {
for (int j = 0; j < adjvexs[i].length; j++) {
if(adjList[i].firstedge == null)
adjList[i].firstedge = new EdgeNode(adjvexs[i][j], null);
else {
getAdjvex(adjList[i]).next = new EdgeNode(adjvexs[i][j], null);
}
}
}
}
TopologySort t = new TopologySort();
System.out.println(t.ToplogicalSort());
}
}
该算法的时间复杂度为O(n+e)。