BFS循環檢測

有人可以通過使用BFS在有向/無向圖中搜索循環來提供逐步僞代碼嗎？BFS循環檢測

它能得到O（| V | + | E |）的複雜性嗎？

到目前爲止，我只看到過DFS的實現。

2017-01-30 ao.

你爲什麼要使用BFS？你一定要嗎？如果沒有，閱讀此，你可能更喜歡使用DFS：http://stackoverflow.com/questions/2869647/why-dfs-and-not-bfs-for-finding-cycle-in-graphs – kazu

@ kazu我想看看它是如何實現的，因爲我的實現被搞砸了。 –

你只需要知道一個循環是否存在或你需要提取特定的圓圈本身？ – Codor

您可以採取非遞歸 DFS算法，您可以用隊列替換節點堆棧以獲得BFS算法。這是簡單的：

q <- new queue // for DFS you use just a stack 
append the start node of n in q 
while q is not empty do 
    n <- remove first element of q 
    if n is visited 
     output 'Hurray, I found a cycle' 
    mark n as visited 
    for each edge (n, m) in E do 
     append m to q

由於BFS訪問每個節點和每條邊只有一次，你有一個的Ø複雜（| V | + | E |）。

來源

2017-01-30 13:15:24 clemens

什麼是非遞歸DFS？你能提供僞碼嗎？我試圖實施，但無法使其工作。 –

我已將算法添加爲僞代碼。 – clemens

謝謝。我們必須使用隊列嗎？你如何打印？ –

我覺得BFS算法非常適合。時間複雜度是相同的。

你想是這樣的（維基百科編輯）：

Cycle-With-Breadth-First-Search(Graph g, Vertex root): 

    create empty set S 
    create empty queue Q  

    root.parent = null 
    Q.enqueueEdges(root)      

    while Q is not empty: 

     current = Q.dequeue() 

     for each node n that is adjacent to current: 
      if n is not in S: 
       add n to S 
       n.parent = current 
       Q.enqueue(n) 
      else //We found a cycle 
       n.parent = current 
       return n and current

我只添加了其他的週期塊週期檢測和移除探測目標的原始如果達到目標塊。總的來說，它是相同的算法。

要找到確切的週期，你將不得不爲n和當前找到一個共同的祖先。最低的一個可用於O（n）時間。比周期是已知的。祖先對n和當前。電流和n連接。

有關週期和BFS更多信息閱讀此鏈接https://stackoverflow.com/a/4464388/6782134

來源

2017-02-17 02:36:02 Dolev

回答

相關問題