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

Question

所以，我试图在有向图中使用 DFS 找到一个循环。现在，我知道如果不可能对图进行拓扑排序，则该图包含一个环。我为拓扑排序制定了以下算法。我不确定我应该在哪里修改此代码以返回 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 的拓扑排序运行并创建一些顶点排序。现在遍历所有边缘并检查它们是否正确定向。如果所有边的方向都正确，则没有循环，否则至少有一个。