package com.example.algorithm4.graphs;
* 有向无环图的 拓扑排序
* @author 惜暮
* @email chris.lyt@alibaba-inc.com
* @date 2017/12/7
public class Topological {
* 顶点的拓扑排序
private Iterable<Integer> order;
public Topological(Digraph digraph){
DirectedCycle cycleFinder = new DirectedCycle(digraph);
if( !cycleFinder.hasCycle() ) {
DepthFirstOrder dfs = new DepthFirstOrder(digraph);
order = dfs.reversePost();
public Iterable<Integer> order() {
return order;
public boolean isDAG(){
return order!=null;
Topological的实现借助了DirectedCycle 检测环是否存在,借助DepthFirstOrder的逆后续来获取拓扑排序。
定理:一幅有向无环图的拓扑排序就是所有顶点的逆后续排列。
在任意一条边v->w, 在调用dfs(v) 时,下面三种情况,必有一种成立:
(1)dfs(w) 已经被调用过了,且已经返回了。 (w节点已经被标记true了)
(2)dfs(w)还没有被调用(w还没被标记), 因此v->w 会直接或则间接调用并返回dfs(w),且dfs(w)会在dfs(v)之前返回。
(3)dfs(w)已经被调用但还没返回。证明的关键在于,在DAG中,这种情况是不可能出现的。由于递归调用链的特性意味着存在从w到v的路径,但又存在v->w的边,所以存在一个环。
在上面(1)(2)两种情况中dfs(w) 会在dfs(v)之前完成,也就是后续排列中w排在v之前。 所以在逆后序中w排在v之后,因此任意一条边v->w 都如我们所愿地从排名比较靠前的顶点指向排名靠后的顶点。
定理:使用深度优先算法对有向无环图进行拓扑排序所需要时间和 (V+E) 成正比。
证明:从DirectedCycle和DepthFirstOrder的实现可知,两次搜索都访问了所有顶点和边,所以时间和(V+E)成正比。
下面给出了一个示例 DAG 的逆后续是拓扑排序的轨迹图: