使用DFS检查无向图中的周期？

Question

所以，我为DFS下面的代码：

void dfs (graph * mygraph, int foo, bool arr[]) // here, foo is the source vertex 
{ 
    if (arr[foo] == true) 
     return; 
    else 
    { 
     cout<<foo<<"\t"; 
     arr[foo] = true; 
     auto it = mygraph->edges[foo].begin(); 
     while (it != mygraph->edges[foo].end()) 
     { 
      int k = *it; 
      if (arr[k] == false) 
      { 
       //cout<<k<<"\n"; 
       dfs(mygraph,k,arr); 
       //cout<<k<<"\t"; 
      } 
      it++; 
     } 
    } 
    //cout<<"\n"; 
} 

现在，我读了，在一个无向图，如果在DFS，再次回到同一个顶点，有一个周期。因此，我做的是这样的，

bool checkcycle(graph * mygraph, int foo, bool arr[]) 
{ 

    bool result = false; 
    if (arr[foo] == true) 
    { 
     result = true; 
    } 
    else 
    { 
     arr[foo] = true; 
     auto it = mygraph->edges[foo].begin(); 
     while (it != mygraph->edges[foo].end()) 
     { 
      int k = *it; 
      result = checkcycle(mygraph,k,arr);  
      it++; 
     } 
    } 
    return result; 
} 

但是，即使它们没有循环，我的checkcycle函数也会返回true。这是为什么？我的功能有问题吗？没有执行问题，否则我会调试，但他们似乎在我的逻辑中是错误的。

Answer 1

注意，你的功能并没有完全做你认为它。让我试着通过这里发生的一切。假设以下关系：（1,2），（1,3），（2,3）。我没有假设灵活性（即（1,2）并不意味着（2,1））。关系是直接的。

1. 开始与节点1将其标记为访问
2. 迭代其子（2,3）
3. 当节点2，递归调用check cycle。此时2还被标记为已访问。
4. 递归调用现在访问3（深度搜索）。 3也被标记为已访问
5. 呼叫步骤4的模具返回false
6. 征集第3步模具返回false
7. 我们回到第2步现在，我们将遍历节点3，它已经被标记在步骤4.它只是返回true。

您需要一堆访问节点，或者您只需搜索原始节点。堆栈将检测子周期以及（循环不包括在原始节点），但它也需要更多的存储器。

编辑：节点堆栈不只是一堆true/false值，而是一堆节点号码。如果存在于堆栈中，则当前堆栈跟踪中已经访问了一个节点。

但是，有一个更友善的方式：设置arr[foo] = false;作为呼叫死亡。事情是这样的：

bool checkcycle(graph * mygraph, int foo, bool arr[], int previousFoo=-1) 
{ 
    bool result = false; 
    if (arr[foo] == true) 
    { 
     result = true; 
    } 
    else 
    { 
     arr[foo] = true; 
     auto it = mygraph->edges[foo].begin(); 
     while (it != mygraph->edges[foo].end()) 
     { 
      int k = *it; 

      // This should prevent going back to the previous node 
      if (k != previousFoo) { 
       result = checkcycle(mygraph,k,arr, foo); 
      } 

      it++; 
     } 

     // Add this 
     arr[foo] = false; 
    } 
    return result; 
} 

我认为它应该是足够了。

编辑：现在应该支持无向图。 节点：这个代码是没有测试

编辑：用于更复杂的解决方案看Strongly Connected Components

编辑：这个答案是市场所接受虽然具体的解决方案是在注释中给出。阅读评论的细节。

Answer 2

都在改编的布尔变量的[]设置为false checkcycle开始之前？

你确定你的节点迭代器不加倍回边它已经走过（因此起始节点多次看到的周期如何）？