使用DFS检测有向图中的周期？

所以，我试图在有向图中找到一个使用DFS的循环。现在，我知道如果图的拓扑排序是不可能的，那么图就包含一个循环。我为拓扑排序做了以下算法。我不知道应该在哪里修改此代码，以便return true或false以及检查我的图是否包含循环。这里是我使用的算法：使用DFS检测有向图中的周期？

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)

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

谢谢！

来源

2015-07-21 John Lui

顺便说一句，为什么C++标签？ – Petr

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

使用三个顶点状态：“未探测”，“正在探索”和“充分探索”。当你输入一个新的顶点时，将它设置为“正在探索”，当你完成一个顶点时，将它设置为“完全探索”。现在，当你遍历某个顶点的邻居时，如果你来到一个“正在探索”的顶点，那么就有一个循环。

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

来源

2015-07-21 15:24:19 Petr

我推荐阅读“算法 - 介绍”（Cormen等人）中的相应部分。

基本上你需要检测，当你重新审视非成品顶点：

相反做上标记顶点V作为探讨/未知你添加一个额外的标签上载明“currently_explored”。每个顶点在开始时标记为未探索（如同时刻）。但它在DFS的第1步中标记为“currently_explored”（而不是探索），并在DFS中的for循环2之后标记为探索。

在DFS中递归调用之前，请检查状态。如果它未被发现，只需递归调用（与当前一样）。如果它目前正在搜索，您已经检测到一个循环！（这是“探索”，这被称为前沿，在这里没有进一步的兴趣）。

请注意，这可以集成到拓扑排序算法0（我建议你也可以在Cormen中查看）。

来源

2015-07-21 15:26:20

对于无向图只需按照以下步骤 -

1）替代布尔访问数组，使它的int类型与初始化为-1的所有指标。

这里-1 = 没有探讨，0 = 正在探讨，1 = 充分探讨

2）初始化的全局布尔变量标志为假。

这里真= 包含周期，假= 不包含周期

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; 
}

来源

2017-04-04 10:43:06

使用DFS检测有向图中的周期？

回答

相关问题