深さ優先探索はグラフ探索アルゴリズムの一種であり、木構造やグラフ構造の探索に広く使われています。深さ優先探索では、あるノードから始まり、そのノードから伸びる子ノードを優先的に探索していきます。その探索が行き詰まった場合には、一つ前のノードに戻り、別の子ノードを探索していくという方法を繰り返していきます。以下では、Pythonで深さ優先探索を実装する手順を説明します。
深さ優先探索とは
深さ優先探索（Depth-First Search, DFS）とは、グラフ探索アルゴリズムの一つであり、あるノードから始まり、そのノードから伸びる子ノードを優先的に探索していきます。その探索が行き詰まった場合には、一つ前のノードに戻り、別の子ノードを探索していくという方法を繰り返していきます。深さ優先探索は再帰的に実装することができ、スタックを用いて非再帰的に実装することもできます。深さ優先探索は、木構造やグラフ構造の探索に広く使われています。
準備
まずは、深さ優先探索を行うグラフのデータ構造を用意しましょう。例として、以下のようなグラフを考えます。
A -- B -- C | | D E
このグラフを辞書で表現すると、以下のようになります。
graph = {'A': set(['B', 'D']),
'B': set(['A', 'C', 'E']),
'C': set(['B']),
'D': set(['A']),
'E': set(['B'])}
この辞書では、グラフの各ノードがキーとして、そのノードから伸びる子ノードの集合が値として格納されています。
深さ優先探索の実装
深さ優先探索は再帰的な呼び出しで実装することができます。具体的なコードは以下のようになります。
def dfs(graph, start, visited=None): if visited is None: visited = set() visited.add(start) for next_node in graph[start] - visited: dfs(graph, next_node, visited) return visited
この関数では、探索を開始するノードとしてstartを受け取り、探索済みのノード集合をvisitedに格納します。visitedがNoneの場合は、空の集合を作成します。次に、現在のノードから伸びる子ノードのうち、まだ探索していないノードを再帰的に探索していきます。これを繰り返していくことで、グラフの全てのノードを探索することができます。実行結果実行例として、以下のようにdfs関数を呼び出してみます。
>>> dfs(graph, 'A') {'A', 'B', 'C', 'D', 'E'}
このようにdfs関数にグラフのデータ構造と探索を開始するノードを指定することで、深さ優先探索を行うことができます。返り値として探索済みのノードの集合が得られます。
まとめ
Pythonで深さ優先探索の実装手順を説明しました。深さ優先探索は、グラフ探索において重要なアルゴリズムの一つであり、そのアルゴリズムは再帰的に実装することができます。再帰を用いた実装は、再帰の考え方を理解する上でも役立ちます。ただし、再帰が深くなりすぎるとスタックオーバーフローが発生する可能性があるため、注意が必要です。深さ優先探索は、幅優先探索と比較して、探索領域が限定されたグラフでの探索に向いています。グラフの構造に応じて、適切な探索アルゴリズムを選択しましょう。
問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本 [ 米田優峻 ]
