深さ優先探索アルゴリズム（DFS）の概要
1. 概要
グラフ理論では、主要なトラバーサルアルゴリズムの1つは DFS （深さ優先探索）です。 このチュートリアルでは、このアルゴリズムを紹介し、再帰的方法と非再帰的方法の両方での実装に焦点を当てます。
まず、DFSアルゴリズムがどのように機能するかを説明し、recursiveバージョンがどのように見えるかを確認します。 また、アルゴリズムが特定のグラフをどのようにトラバースするかを確認する例を示します。
次に、非再帰バージョンの背後にある考え方を説明し、その実装を示し、両方のバージョンがサンプルグラフをどのように処理するかを示す例を示します。
最後に、再帰バージョンと非再帰バージョンの両方を比較し、それぞれをいつ使用するかを示します。
2. 定義
一般的なDFSアルゴリズムの定義から始めて、アルゴリズムがどのように機能するかを確認するための例を示します。
2.1. 一般的な概念
DFSアルゴリズムは、開始ノードから開始します。 各ステップで、アルゴリズムは隣接するノードの中から訪問されていないノードの1つを選択し、そのノードから開始して再帰呼び出しを実行します。 ノードのすべてのネイバーが訪問されると、アルゴリズムはそのノードに対して終了し、ノードへの呼び出しを開始したノードのネイバーをチェックするために戻ります。
とは異なり BFS アルゴリズム、
簡単にするために、グラフは隣接リストデータ構造で表されていると仮定します。 説明したすべてのアルゴリズムは、他のデータ構造の場合に適用するように簡単に変更できます。
2.2. 例
次のグラフの例を考えてみましょう。
ノードからDFS操作を開始するとします。 隣接リスト内のすべての隣接ノードがアルファベット順に昇順であると仮定しましょう。 次の操作を実行します。
- から始めて、2つのネイバー、、、があります。 したがって、から続行します。
- 未訪問の隣接するものが1つしかないため、その1つから続行します。
- ノードには、2つの未訪問のネイバーとがあります。 したがって、ノードから続行します。
- 未訪問のネイバーが1つだけあります。 そこで、に移動します。
- 同様に、訪問されていない隣接するものは1つだけです。 したがって、次のノードはである必要があります。 も隣接していることに注意してください。 ただし、これらのノードはすでにアクセスされています。
- それだけが未訪問です。 したがって、に移動します。
- 最後に、ノードには未訪問のネイバーがありません。 アルゴリズムは、、、、、、、そしてに後退します。 これらのノードには、未訪問の隣接ノードはありません。 したがって、アルゴリズムは単に終了します。
その結果、訪問したノードの最終的な順序は{}になります。
3. 再帰的DFS
DFSアルゴリズムの再帰バージョンを紹介しましょう。 実装を見てください：
まず、値で初期化される配列を定義します。 配列の使用は、アルゴリズムが同じノードに複数回アクセスするのを防ぐために、どのノードにアクセスしたかを判別することです。
配列の準備ができたら、関数を呼び出します。
この関数は、ノードにアクセスしたかどうかを確認することから始まります。 その場合、それ以上のアクションを実行せずに戻るだけです。
ただし、ノードが訪問されていない場合、関数はノードを出力します。また、関数はノードを訪問済みとしてマークし、後のステップでノードが再訪問されないようにします。
ノードが処理されたので、隣接ノードを反復処理できます。 それぞれについて、関数を再帰的に呼び出します。
再帰バージョンの複雑さはです。ここで、はノードの数、はグラフ内のエッジの数です。
複雑さの背後にある理由は、関数によって各ノードに1回だけアクセスするためです。 また、ノードごとに、隣接ノードを1回だけ繰り返します。 したがって、グラフ内の各エッジを2回調べます。 エッジがとの間にあると仮定すると、初めて、の隣接として探索し、2回目では、の隣接として検出します。
したがって、合計で、内部ループは実行回数を取得します。
再帰的なDFSバージョンについて十分に理解したので、それを更新して反復（非再帰的）にすることができます。
4. 反復DFS
再帰的なDFSバージョンを分析することから始めましょう。 それから、反復的なアプローチを段階的に構築できます。
4.1. 再帰的アプローチの分析
再帰的なDFS擬似コードを読んだ後、次のことに気付くことができます。
- 各ノードについて、DFS関数は隣接するノードを1つずつ探索します。 ただし、この関数は、アクセスされていないものに対してのみ再帰呼び出しを実行します。
- 隣接ノードを探索する場合、DFS機能が探索する次のノードは、隣接リスト内の最初の未訪問ノードです。 この順序を尊重する必要があります。
- DFS関数は、ノードに接続されているサブグラフ全体へのアクセスを終了すると、終了して前のノード（ノードで再帰呼び出しを実行したノード）に戻ります。
- それがどのように機能するかは、プログラムが関数の現在のパラメーターと変数をスタックにプッシュすることです。 再帰呼び出しが終了すると、プログラムはスタックからこれらの変数を取得し、実行を続行します。 したがって、手動スタックを使用して、再帰DFSを反復バージョンに更新する必要があります。
上記のメモを使用して、反復バージョンを作成しましょう。
4.2. 理論的アイデア
私たちがする必要があるのは、プログラムスタックの作業をシミュレートすることです。 まず、開始ノードをスタックにプッシュしましょう。 次に、複数のステップを実行できます。
各ステップで、スタックから要素を抽出します。 これは、DFS関数の新しい再帰呼び出しを開始するのと似ているはずです。 スタックからノードをポップすると、その隣接ノードを反復処理できます。
抽出されたノードの隣接ノードにアクセスするには、それらもスタックにプッシュする必要があります。 ただし、ノードをスタックにプッシュしてから次のノードを抽出すると、最後のネイバーが取得されます（スタックが先入れ先出しとして機能するため）。
したがって、隣接リスト内での表示とは逆の順序でノードをスタックに追加する必要があります。 この手順は、再帰バージョンと同じ順序に従う必要がある場合にのみ必須であることに注意してください。 隣接リスト内のノードの順序を気にしない場合は、それらを任意の順序でスタックに追加することもできます。
その後、スタックからノードを抽出し、そのノードにアクセスして、隣接するノードを反復処理します。 このプロセスは、スタックが空になるまで続行する必要があります。
アルゴリズムの主なアイデアをリストした後、きちんとした反復実装を整理できます。
4.3. 実装
反復DFSの実装を見てみましょう。
再帰バージョンと同様に、これまでに各ノードにアクセスしたかどうかを示す値を使用して配列を初期化します。 ただし、反復バージョンでは、再帰バージョンのプログラムスタックをシミュレートする空のスタックも初期化します。
次に、開始ノードをスタックにプッシュします。 その後、再帰バージョンと同様の複数の手順を実行します。
各ステップで、スタックからノードを抽出します。これは、新しい再帰的なDFS呼び出しの入力をシミュレートします。 次に、このノードに既にアクセスしたかどうかを確認します。 実行した場合は、ノードを処理したり、隣接ノードにアクセスしたりせずに続行します。
ただし、ノードが訪問されていない場合は、その値（ノードを処理したことを示す）を出力し、訪問済みとしてマークします。 また、隣接するすべてのものを繰り返し処理して、スタックにプッシュします。 隣接するものをスタックにプッシュすることは、それらのそれぞれに対して再帰的な呼び出しを実行することをシミュレートします。
それにもかかわらず、反復バージョンでは、逆の順序でネイバーを反復処理する必要があります。 したがって、はの隣接を逆の順序で返すと仮定します。
また、すべてのネイバーをスタックにプッシュする代わりに、訪問していないネイバーのみをプッシュします。 この手順は不要ですが、結果に影響を与えることなく、スタック内のノードの数を減らすことができます。
反復アプローチのステップは再帰的アプローチと同じであるため、複雑さはです。ここで、はノードの数、はグラフ内のエッジの数です。
5. 例
次のグラフの例を考えてみましょう。
再帰的および非再帰的DFSバージョンがこのグラフのノードをどのように出力するかを見てみましょう。
再帰的DFSの場合、以下の例の最初の3つのステップを示します。
再帰呼び出しがまだ終了していないノードは、青色でマークされていることに注意してください。
まず、ノードから始めます。 隣接するノードを探索するため、2番目のステップでノードに移動します。 ノードのネイバーを探索した後、ノードに進みます。
次の3つのステップがどのようになるか見てみましょう。
この例では、再帰関数が終了したノードがいくつかあります。 これらのノードは赤い色でマークされています。
ノードからその隣人を探索し、そこに移動します。
今、物事はトリッキーになります。 訪問していない隣人がいないことに気づきました。 したがって、ノードで再帰呼び出しを終了し、ノードに戻ります。
ただし、ノードには、訪問されていない隣接ノードもありません。 したがって、再帰呼び出しも終了し、ノードに戻ります。
ノードには、ノードである非訪問ネイバーがあることがわかります。 したがって、ノードから開始して再帰呼び出しを実行します。 ただし、ノードにはアクセスされていないノードがないようです。 したがって、関数はノードに戻ります。
ノードのすべての隣接を訪問し終えたので、関数はノードに戻ります。 ノードに未訪問のノードがもうないことがわかります。 したがって、関数は停止します。
その結果、訪問したノードが順番に{}であることがわかります。
それでは、反復アプローチがグラフの例をどのように処理するかを確認しましょう。
5.1. 反復DFS
反復DFSの場合、最初の3つのステップを検討してください。
反復DFSでは、手動スタックを使用して再帰をシミュレートします。 スタックは青色でマークされています。 また、これまでに訪問したすべてのノードは赤い色でマークされています。
最初に、最初のステップでノードをスタックに追加します。 スタックからノードをポップすると、訪問されます。 そのため、赤い色でマークしました。 ノードにアクセスしたので、そのすべてのネイバーを逆の順序でスタックに追加します。
次に、スタックからポップして、アクセスされていないすべてのネイバーとをプッシュします。 この場合、スタックにノードを再度追加します。 ノードはとの両方に隣接しているため、これは完全に問題ありませんが、まだアクセスされていません。
反復アプローチの次の3つのステップを見てみましょう。
スタックからノードをポップし、訪問済みとしてマークし、隣接するをプッシュします。
次のステップは、抽出して訪問済みとしてマークすることです。 ただし、この場合、ノードには未訪問のネイバーはありません。 したがって、この場合、スタックには何もプッシュしません。
次にポップするノードはノードです。 同様に、私たちはすでにすべての隣人を訪問したので、その場所に何もプッシュしません。
すべてのノードにアクセスした後も、まだノードがあり、スタック内にあります。 したがって、これらのノードをポップして続行します。これは、すでに両方のノードにアクセスしているためです。
再帰的アプローチと同様の訪問順序が得られたことに注意してください。 訪問の順番も{}です。
再帰的アプローチと反復的アプローチはどちらも同じ複雑さを持っています。 したがって、実装が簡単なため、通常は再帰的アプローチを使用する方が簡単です。
ただし、まれに、プログラムのスタックのサイズが小さい場合、反復アプローチを使用する必要がある場合があります。 その理由は、プログラムが手動スタックをヒープスペース内に割り当てるためです。これは通常、スタックスペースよりも大きくなります。
6. 結論
このチュートリアルでは、深さ優先探索アルゴリズムを紹介しました。 まず、アルゴリズムが一般的にどのように機能するかを説明し、再帰バージョンの実装を示しました。
次に、再帰的アプローチを繰り返し実装する方法を示しました。
その後、両方のアプローチの段階的な例を示し、結果を比較しました。
最後に、各アプローチをいつ使用するかを示す簡単な比較で要約しました。
