判断有向图是否有环

要判断一个有向图是否有环，我们可以选择选择BFS, DFS 或者 Topological sorting. 用BFS或者DFS进行判断时，我们主要判断要被访问的node是否已经被访问过，如果被访问过，就有环。利用topological sorting进行判断的时候，就是判断node是否只有一个node和它连接(算法第八行)（按照树的说法，也就是看那个点是否只有一个父节点）。

代码如下（来自wiki）：

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    output error message (graph has at least one cycle)
else 
    output message (proposed topologically sorted order: L)

参考：http://en.wikipedia.org/wiki/Topological_sorting