BFSサイクル検出

Question

誰かがBFSを使用してステップバイステップ疑似コードを提供して、有向グラフまたは無向グラフでサイクルを検索できますか？

O（| V | + | E |）の複雑さは得られますか？

これまではDFSの実装しか見ていませんでした。

Answer 1

非再帰的 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は、各ノードを訪問し、一度だけ、各エッジは、あなたがOの複雑さがあるので（| V | + | Eを|）。

Answer 2

私はそれに最適な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を使用したいのはなぜサイクルとBFSについての詳細情報については

は、このリンクhttps://stackoverflow.com/a/4464388/6782134