graph-algorithm - BFS サイクル検出

Question

誰かが有向/無向グラフでサイクルを検索するために BFS を使用して段階的な疑似コードを提供できますか?

O(|V|+|E|) の複雑さを得ることができますか?

これまでのところ、DFS の実装しか見たことがありません。

Answer 1

ノードのスタックをキューに置き換えて BFS アルゴリズムを取得する無向グラフでサイクルを検出するために、非再帰的なDFS アルゴリズムを使用できます。それは簡単です：

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|) になります。