最小生成树和最短路径可以解决无序的问题，此处的无序指的是对顶点的访问顺序没有要求，但是很多场景对顺序有严格的要求，比如说建造一栋大楼必须先找好施工人员，购买各种材料和准备好各种器械之后才能开始盖楼。或者是拍电影必须先找好演员和各种负责人之后才能开拍。类似这样的场景我们称为AOV网。
在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网（Activity On Vertex Network）。
AOV网中不能存在回路，因为后续的活动依赖之前的活动，而不能互相依赖。而拓扑排序，就是对这样的AOV网进行排序，它的定义如下：
设G=(V, E)是一个具有 n 个顶点的有向图，V中的顶点序列v0, v1, ..., vn-1，满足若从顶点 vi 到 vj 有一条路径，则在顶点序列中顶点 vi 必在 vj 之前，这样的顶点序列就是拓扑序列。将AOV网排序成这样的序列就是拓扑排序。
例如下图就是一个AOV网，其中v2、v3、v4、v5都依赖于v1，表明只要v1执行完毕后，它们都可以开始了。
对于这样的AOV网，只要v0在v1之前，v1在v2、v3、v4、v5之前，而v2、v3在v6之前，v4、v5在v7之前，v6和v7在v8之前，就是一个有效的拓扑序列。比如可以是v0->v1->v2->v3->v4->v5->v6->v7->v8，也可以是v0->v1->v2->v3->v6->v4->v5->v7->v8。
拓扑排序的思路就是：从AOV网中选择一个入度为0的顶点，删除它与其它顶点间的弧，然后重复这个过程，直到得到全部顶点，或者是判断出它不是一个AOV网。
因为涉及到大量的删除操作，我们选择邻接表来存储数据，同时为了方便计算入度，增加一个属性来记录每个顶点的入度。拓扑排序的参考代码如下：
public <T> boolean topoSort(ATGraph<T> atGraph) {
int count = 0;
Queue<ATVertex<T>> queue = new LinkedList<>();
for (int i = 0; i < atGraph.getLen(); i++) {
if (atGraph.getVertex(i).getIn() == 0) {
queue.offer(atGraph.getVertex(i));
}
}
while (!queue.isEmpty()) {
ATVertex<T> vertex = queue.poll();
System.out.print(vertex.getData() + "->");
count++;
ATEdge<T> next = vertex.getNext();
while (next != null) {
ATVertex<T> nextVertex = next.getVertex();
nextVertex.setIn(nextVertex.getIn() - 1);
if (nextVertex.getIn() == 0) {
queue.offer(nextVertex);
}
next = next.getNext();
}
}
return count >= atGraph.getLen();
}
我是飞机酱，如果您喜欢我的文章，可以关注我~
编程之路，道阻且长。唯，路漫漫其修远兮，吾将上下而求索。
