広範な最初の検索を使用してグラフ内のサイクルを見つけるための擬似コード

Question

BFSを使用してサイクルを見つけるための擬似コードを与えてください。私はこのタイプの他の質問があることを知っていますが、NONEはコードを与えません。

Answer 1

DFSは、タスクにはるかに適しており、さらに有向グラフではより適しています。既に知っていたら、これを無視してください。

擬似コードに関しては、無向グラフでは、これは以前に訪問済みとしてマークされたノードに到達したときに見つかったサイクルを中止し報告する従来のBFSです。あなたはBFS hereの擬似コードを見つけることができます。

有向グラフでは、ノードに到達したときにどの方向に歩いていたのかを覚えておく必要があり、DFSより空間的に複雑な欠点がさらに悪化します。

編集：ああ、私はサイクルのグラフをテストすることについて話していましたが、実際にサイクルを見つけることはありませんでした。 DFSのサイクルを見つけることは簡単なことではありませんが、BFSのサイクルを見つけることは実際のアルゴリズムの複雑さとコードの複雑さの両方ではるかに複雑です。そのため、擬似コードが見つからないのです。

Answer 2

おそらくDFSを意味していますが、これはサイクル検出ではるかに一般的です。間違えたと思います。 BFSへの変更はかなり簡単ですが、コアの考え方は変わりません。

func detectCycle() 
    for node in graph: 
    visited = bool[N] 
    set all visited to false 
    detectCycle(n, n, visited) 

func detectCycle(n, origin, visited) 
    for neighbour in graph[n] 
    if neighbour == origin 
     cycle detected 
    if not visited[neighbour] 
     visited[neighbour] = true 
     detectCycle(neighbour, visited) 
     visited[neighbour] = false