データ構造-深さ優先探索
深さ優先探索(DFS)アルゴリズムは、グラフを深さ方向に移動し、スタックを使用して、反復で行き止まりが発生したときに、次の頂点を取得して検索を開始することを記憶します。
上記の例のように、DFSアルゴリズムは、最初にSからA、D、G、E、B、次にF、最後にCに移動します。次のルールを採用しています。
Rule 1−隣接する未訪問の頂点にアクセスします。訪問済みとしてマークします。表示します。スタックにプッシュします。
Rule 2−隣接する頂点が見つからない場合は、スタックから頂点をポップアップします。(隣接する頂点がないスタックからすべての頂点がポップアップ表示されます。)
Rule 3 −スタックが空になるまで、ルール1とルール2を繰り返します。
ステップ | トラバーサル | 説明 |
---|---|---|
1 |
|
スタックを初期化します。 |
2 |
|
マーク S訪問したとおりにスタックに置きます。からの未訪問の隣接ノードを探索しますS。3つのノードがあり、それらのいずれかを選択できます。この例では、ノードをアルファベット順に取り上げます。 |
3 |
|
マーク A訪問したとおりにスタックに置きます。Aから未訪問の隣接ノードを探索します。両方S そして D に隣接しています A ただし、未訪問のノードのみを対象としています。 |
4 |
|
訪問 D訪問済みとしてマークし、スタックに置きます。ここに、B そして C 隣接するノード Dそして両方とも訪問されていません。ただし、ここでもアルファベット順に選択します。 |
5 |
|
我々が選択しました B、訪問済みとしてマークし、スタックに置きます。ここにB未訪問の隣接ノードはありません。だから、私たちはポップしますB スタックから。 |
6 |
|
スタックトップが前のノードに戻っているかどうかを確認し、未訪問のノードがあるかどうかを確認します。ここで、D スタックの一番上になります。 |
7 |
|
訪問されていない隣接ノードのみが D です C今。だから私たちは訪問しますC、訪問済みとしてマークし、スタックに置きます。 |
なので C未訪問の隣接ノードがないため、未訪問の隣接ノードがあるノードが見つかるまでスタックをポップし続けます。この場合、何もありません。スタックが空になるまでポップし続けます。
Cプログラミング言語でのこのアルゴリズムの実装について知るには、ここをクリックしてください。