使用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開始之前？

你確定你的節點迭代器不加倍回邊它已經走過（因此起始節點多次看到的週期如何）？