使用DFS检测有向图中的循环？

Question

所以,我试图在有向图中使用DFS找到一个循环.现在,我知道如果图形的拓扑排序不可能,那么图形包含一个循环.我为拓扑排序做了以下算法.我不知道我应该在哪里修改这个代码,以return true或false和检查,如果我的图包含一个周期或没有.这是我使用的算法:

DFS-Loop (Graph G)

1. Mark all vertices as unexplored.
2. Set label = n // number of vertices
3. For each vertex V (belonging to) G
   -- If V not yet explored,
   -- DFS (G,V)
4. Set f(V) = current_label // here, f(V) is basically the position of V in the ordering
5. current_label-- 

Where DFS(G,V) will be something like: 

1. Mark V as explored.
2. For every vertex K belonging to Adj.(V)
   -- If K is not explored, 
   -- Call DFS(G,K)

我应该在哪里添加此检查以包含循环？

谢谢!

Answer 1

在有向图中找到循环的最简单方法如下.

使用三种顶点状态:"未探索","正在探索"和"充分探索".当您输入新顶点时,将其设置为"正在探索",当您完成顶点时,将其设置为"完全探索".现在,当你迭代一些顶点的邻居时,如果你来到一个"正在探索"的顶点,那么就有一个循环.

DFS(G,V):
1. Mark V as "being explored"
2. For every vertex K belonging to Adj.(V)
   -- If K is not explored, 
      -- Call DFS(G,K)
   -- else if K is "being explored" (not "fully explored")
      -- then there is a cycle
3. Mark V as "fully explored" 

您可以通过从找到的"被探索的"顶点回溯来找到循环.

另一种方法是允许基于DFS的拓扑排序运行并创建一些顶点排序.现在迭代所有边缘并检查它们是否正确定向.如果所有边缘都正确定向,那么如果没有循环则存在,否则至少有一个.