一、什么是拓扑排序？
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
二、拓扑排序：基本概念
问题：
假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。
检查有向图是否存在回路的方法之一，是对有向图进行==拓扑排序==。有回路，不是存在拓扑排序；没有回路，存在拓扑排序
一个无环的有向图称为有向无环图（Directed Acycline Graph），简称为DAG图。
通常我们用一个有向图的顶点表示活动，边表示活动间先后关系，这样的有向图称为顶点活动网（Activity On Vertex network），简称AOV网。
工程是否顺利进行
完成整个工程所必须的最短时间
在AOV网表示工程的施工图，若出现==环==，标明该工程的施工设计图存在问题。
若AOV网表示的是数据流图，若出现==环==，标明存在死循环。
拓扑排序：对一个有向图构建拓扑序列的过程。
三、拓扑排序：分析
判断有向网是否存在有向环的一个方法：（对AOV网进行拓扑排序）
构造一个包含图中所有顶点的”拓扑排序序列“。
若在AOV网中存在一条从顶点u到顶点v的弧，则在==拓扑有序序列中顶点u必然优先于顶点v==。
若在AOV网中顶点u和顶点w之间没有弧，则在拓扑有序序列中，这两个顶点的先后次序关系可以==随意==
现有如下课程，并能够绘制下方有向图：
实例1：存在拓扑序列abcefdgh，说明不存在环
实例2：不存在拓扑序列，说明存在环fdghf
四、拓扑排序：步骤
步骤：
1. 在AOV网中选择一个没有前驱的顶点并输出
2. 从AOV网中删除该顶点以及从它出发的弧
3. 重复1和2直到AOV网为空（即已输出所有的顶点），或剩余子图中不存在没有前驱的顶点。后一种情况说明该AOV网中存在有向环。
算法要考虑的问题：
1. “没有前驱”如何判断
2. “删除顶点及以它为尾的弧”如何操作
解决方法：
1. 以==入度为零==作为没有前驱的量度
2. 算法中预设一个栈，用于保存当前出现的入度为零的顶点
3. 删除顶点及以它为尾的弧的这类操作，可用“弧头顶点的入度减1”的办法来替代。
五、拓扑排序：实现
由于拓扑排序中对图的主要操作是“找从顶点出发的弧”，并且AOV网在多数情况下是稀疏图，因此存储结构取==邻接表==为宜
public class TopologicalSort { // 拓扑排序 public static boolean topologicalSort(ALGraph G) throws Exception { int count = 0;// 输出定点计数 int[] indegree = findInDegree(G);// 求各顶点入度 LinkStack S = new LinkStack();// 建零入度顶点栈 for (int i = 0; i < G.getVexNum(); i++) if (indegree[i] == 0)// 入度为0者进栈 S.push(i); while (!S.isEmpty()) { int i = (Integer) S.pop(); // 栈不空 取栈顶元素 System.out.print(G.getVex(i) + " ");// 输出V号顶点 并 计数 ++count; for (ArcNode arc = G.getVexs()[i].firstArc; arc != null; arc = arc .nextArc) { int k = arc.adjVex; if (--indegree[k] == 0)// 对i号顶点的每个邻接点的入度减1 S.push(k);// 若入度减为0，则入栈 } } if (count < G.getVexNum()) return false;//该有向图有回路 else return true; } //求各顶点入度 算法6.11 public static int[] findInDegree(ALGraph G) throws Exception { int[] indegree = new int[G.getVexNum()]; for (int i = 0; i < G.getVexNum(); i++) for (ArcNode arc = G.getVexs()[i].firstArc; arc != null; arc = arc .nextArc) ++indegree[arc.adjVex];// 入度增加1 return indegree; } public static void main(String[] args) throws Exception { ALGraph G = GenerateGraph.generateALGraph(); TopologicalSort.topologicalSort(G); } } // 调试结果： // v1 v2 v3 v5 v7 v4 v6 v8 v9
- 拓扑排序算法总的时间复杂度：O(n+e)
六、练习
试列出下图中，全部可能的拓扑有序序列：
