algorithm - 有向グラフでの DFS および BFS の実行

Question

次のようなグラフがあるとします。

0 から 5 までのパスが必要な場合、このグラフで DFS と BFS を実行する場合、どの順序でノードにアクセスしますか (最下位の要素が常に最初にプッシュされると仮定します)。サイクルのあるグラフでアルゴリズムがどのように機能するかを概念化するのに苦労しています。誰かがそのようなグラフでそれぞれが取る手順の概要を説明できることを望んでいました。

Answer 1

サイクルを処理するために使用される一般的な手法は、既に訪れた頂点のセットを持つことです。頂点をキュー/スタックにプッシュする前に、アクセスしたかどうかを確認してください。何もアクションを実行しない場合は、訪問済みセットに追加することから始めてから、グラフのトラバースを続けます。

上から下に積み重ねます。

DFS:

empty stack
visiting 0: stack: 2, 1, visited: 0
visiting 2: stack: 5, 3, 1 visited: 0, 2
visiting 5: stack: 4, 3, 1 visited: 0, 2, 5
visiting 4: stack: 3, 2, 3, 1 visited: 0, 2, 4, 5
visiting 3: stack: 4, 2, 3, 1 visited: 0, 2, 3, 4, 5
visiting 4: (nothing to do) - stack: 2, 3, 1 visited: 0, 2, 3, 4, 5
visiting 2: (nothing to do) - stack: 3, 1 visited: 0, 2, 3, 4, 5
visiting 3: (nothing to do) - stack: 3, 1 visited: 0, 2, 3, 4, 5
visiting 1: stack: 3, 0 visited: 0, 1, 2, 3, 4, 5
visiting 3: (nothing to do) - stack: 1 visited: 0, 1, 2, 3, 4, 5
visiting 1: (nothing to do) - stack empty visited: 0, 1, 2, 3, 4, 5
DONE

同様の方法で BFS を行います。