本文将从以下几个方面介绍拓扑排序：
典型实现算法解的唯一性问题实际例子
取材自以下材料：
定义和前置条件：
Directed Acyclic Graph)。
偏序和全序实际上是离散数学中的概念。
这里不打算说太多形式化的定义，形式化的定义教科书上或者上面给的链接中就说的很详细。
实际上，很多地方都存在偏序和全序的概念。
拓展到拓扑排序中，结果具有唯一性的条件也是其所有顶点之间都具有全序关系。如果没有这一层全序关系，那么拓扑排序的结果也就不是唯一的了。在后面会谈到，如果拓扑排序的结果唯一，那么该拓扑排序的结果同时也代表了一条哈密顿路径。
典型实现算法：
Kahn算法：
L← Empty list that will contain the sorted elementsS ← Set of all nodes with no incoming edgeswhile S is non-empty do remove a node n from S insert n into L foreach node m with an edge e from nto m do remove edge e from thegraph ifm has no other incoming edges then insert m into Sif graph has edges then return error (graph has at least onecycle)else return L (a topologically sortedorder)
实现代码：
public class KahnTopological{private List<Integer> result; // 用来存储结果集private Queue<Integer> setOfZeroIndegree; // 用来存储入度为0的顶点private int[] indegrees; // 记录每个顶点当前的入度private int edges;private Digraph di;public KahnTopological(Digraph di){this.di = di;this.edges = di.getE();this.indegrees = new int[di.getV()];this.result = new ArrayList<Integer>();this.setOfZeroIndegree = new LinkedList<Integer>();// 对入度为0的集合进行初始化Iterable<Integer>[] adjs = di.getAdj();for(int i = 0; i < adjs.length; i++){// 对每一条边 v -> wfor(int w : adjs[i]){indegrees[w]++;}}for(int i = 0; i < indegrees.length; i++){if(0 == indegrees[i]){setOfZeroIndegree.enqueue(i);}}process();}private void process(){while(!setOfZeroIndegree.isEmpty()){int v = setOfZeroIndegree.dequeue();// 将当前顶点添加到结果集中result.add(v);// 遍历由v引出的所有边for(int w : di.adj(v)){// 将该边从图中移除，通过减少边的数量来表示edges–;if(0 == –indegrees[w]) // 如果入度为0，那么加入入度为0的集合{setOfZeroIndegree.enqueue(w);}}}// 如果此时图中还存在边，那么说明图中含有环路if(0 != edges){throw new IllegalArgumentException("Has Cycle !");}}public Iterable<Integer> getResult(){return result;}}
对上图进行拓扑排序的结果：
2->8->0->3->7->1->5->6->9->4->11->10->12
复杂度分析：
然后对该集合进行操作，又需要遍历整张图中的，每条边，复杂度也为O(E+V);
同样摘录一段维基百科上的伪码：
L ← Empty list that will contain the sorted nodesS ← Set of all nodes with no outgoing edgesfor each node n in S do visit(n) function visit(node n) if n has not been visited yet then mark n as visited for each node m with an edgefrom m to ndo visit(m) add n to L
add n to L。
这个算法的实现非常简单，但是要理解的话就相对复杂一点。
下面简单证明一下它的正确性：
实现代码：
public class DirectedDepthFirstOrder{// visited数组，DFS实现需要用到private boolean[] visited;// 使用栈来保存最后的结果private Stack<Integer> reversePost;/** * Topological Sorting Constructor */public DirectedDepthFirstOrder(Digraph di, boolean detectCycle){// 这里的DirectedDepthFirstCycleDetection是一个用于检测有向图中是否存在环路的类DirectedDepthFirstCycleDetection detect = new DirectedDepthFirstCycleDetection(di);if (detectCycle && detect.hasCycle())throw new IllegalArgumentException("Has cycle");this.visited = new boolean[di.getV()];this.reversePost = new Stack<Integer>();for (int i = 0; i < di.getV(); i++){if (!visited[i]){dfs(di, i);}}}private void dfs(Digraph di, int v){visited[v] = true;for (int w : di.adj(v)){if (!visited[w]){dfs(di, w);}}// 在即将退出dfs方法的时候，将当前顶点添加到结果集中reversePost.push(v);}public Iterable<Integer> getReversePost(){return reversePost;}}
复杂度分析：
我不去想是否能够成功，既然选择了远方，便只顾风雨兼程！
