基礎アルゴリズム(四)---深さ優先探索(DFS)

深度優先探索アルゴリズム(Depth-First-Search)は、探索アルゴリズムの一種である.
ツリーの深さに沿ってツリーのノードを巡り、できるだけ深くツリーのブランチを検索します.
ノードvのすべてのエッジが探索されると、探索は、ノードvが発見されたエッジの開始ノードに遡る.このプロセスは、ソースノードから到達可能なすべてのノードが発見されるまで行われます.
発見されていないノードがまだ存在する場合は、いずれかをソースノードとして選択し、すべてのノードがアクセスされるまでプロセス全体を繰り返します.DFSは盲目的検索に属する.
深さ優先探索は図論における古典的なアルゴリズムであり,深さ優先探索アルゴリズムを用いてターゲットマップの対応するトポロジーソートテーブルを生成することができ,トポロジーソートテーブルを用いて最大パス問題など多くの関連する図論問題を容易に解決することができる.DFSアルゴリズムの実装を支援するためにスタックデータ構造が一般的である.
深度優先ループアルゴリズムの手順:

は頂点vにアクセスする.

は、vのアクセスされていない隣接点から順に図を優先的に遍歴する.図中とvに経路が通じる頂点がアクセスされるまで;

この時点で図中の頂点がまだアクセスされていない場合、図中のすべての頂点がアクセスされるまで、1つのアクセスされていない頂点から深さ優先ループを再開する.

上記の説明は抽象的で、例を挙げます.
DFSは、アクセスマップのいずれかの始点頂点vにアクセスした後、vから出発し、そのいずれかの隣接頂点w 1にアクセスする.さらにw 1から出発し、w 1に隣接しているがまだアクセスしていない頂点w 2にアクセスする.そしてw 2から、同様のアクセスを行い、...このようにして、すべての隣接頂点がアクセスされた頂点uに達するまで行う.
次に、前にアクセスしたばかりの頂点に戻り、他にアクセスされていない隣接する頂点があるかどうかを確認します.もしあるならば、この頂点にアクセスして、それからこの頂点から出発して、前述と類似のアクセスを行います;もしなかったら、もう一歩戻って検索します.連通図のすべての頂点がアクセスされるまで、上記の手順を繰り返します.