使用深度优先搜索检测有向图中的循环？

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)

我应该在哪里添加检查是否包含循环的代码？

谢谢！

- John Lui

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的拓扑排序运行并创建一些顶点的排序。现在遍历所有边缘并检查它们是否正确定向。如果所有边缘都被正确定向，则没有循环，否则至少有一个。

- Petr

---

如果 K 是“完全探索”，则应该是 else if K is "fully explored"。如果我使用一个包含2个节点和1条边的图，你的算法会失败。它会将其标记为具有循环。 - undefined

@ManishSharma，请注意图表是有向的。 - undefined

Answer 2

对于无向图，请按以下步骤操作 -

1）将布尔访问数组更改为int类型，并将所有索引初始化为-1。

这里，-1 = 未探索，0 = 正在探索，1 = 完全探索

2）将全局布尔变量标志初始化为false。

这里，true = 包含循环，false = 不包含循环

3）现在编写DFS如下（以下是C++代码） -

void dfs(int s)
{
    visited[s] = 0;
    for(int i = 0; i < adj[s].size(); i++)
    {
        if(visited[ adj[s][i] ] == -1)
        {
            dfs(adj[s][i]);
        }
        else if(visited[adj[s][i]] == 1)
        {
            flag = true;
            return;
        }
    }
    visited[s] = 1;
}

- Manish Sharma

---

visited[adj[s][i]] == 1 是错误的，应该是 visited[adj[s][i]] == 0，也就是在探索顶点时。 - undefined

@suraznegi 我编写的算法适用于无向图，其中情况 visited[adj[s][i]] == 1 是正确的。 - undefined

Answer 3

我建议阅读“算法导论”（Cormen et. al）中对应的章节。

基本上，您需要检测当您重新访问未完成的顶点时：

不要将您的顶点V标记为已探索/未探索，而需添加一个额外的标签状态"currently_explored"。 每个顶点在开始时（此刻）都被标记为未探索。但是，在DFS的第1步骤中，它被标记为“currently_explored”，并在DFS的for-loop 2之后标记为已探索。

在递归调用DFS之前，请检查其状态。如果它没有被探索，则正常递归调用。如果它被标记为"currently_explored"，则您已经检测到了一个循环！（如果它被标记为"explored"，这称为前向边，在此无关紧要）。

请注意，这可以整合到拓扑排序算法中 （我建议您在Cormen中查找此内容）。

- dr.walfeld