使用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檢測有向圖中的週期？

回答

相關問題