このレッスンでは、グラフ探索のための2つの補完的、基本的、かつ最も単純なアルゴリズムの1つである深さ優先探索（DFS）を見ていきます。DFSは、関連するBreadth-First Search (BFS) と共に、その単純さゆえに最もよく使われるアルゴリズムです。DFSの主な考え方を説明した後、PythonでGraph表現である隣接リストに対して実装します。
深層優先探索 – 理論編
深さ優先探索（DFS）は、グラフや木のデータ構造を走査して目的のノードを見つけるために使われるアルゴリズムである。深さを優先し、1つの枝にそって、行けるところまで、その枝の終わりまで探索する。そして、その枝から最初に分岐しそうなところまで戻り、その枝の終わりまで探索し、それを繰り返す。
このアルゴリズムの性質から、再帰的に実装することは容易です。また、再帰的なアルゴリズムは常に反復的に実装することができます。
開始ノードは、木構造データではルートノード、より一般的なグラフでは任意のノードとなる。
DFSは、グラフ表現された問題を解決する他の多くのアルゴリズムの一部とし て広く使われている。サイクル検索、経路探索、位相ソート、連結点および強連結成分の探索などである。このようにDFSアルゴリズムが広く使われている背景には、その全体的な単純さと簡単な再帰的実装がある。
DFSアルゴリズム
DFSのアルゴリズムは非常にシンプルで、以下のステップで構成されています。
- 現在のノードを訪問済みとしてマークする。
-
- 訪問していない隣接ノードを走査し，そのノードのDFS関数を再帰的に呼び出す．
アルゴリズムは、目的のノードが見つかるか、グラフ全体が走査された（すべてのノードが訪問された）時点で停止する。
注：グラフはサイクルを持つことができるので、無限ループに陥らないように、サイクルを回避するシステムが必要であろう。そのため、一意なエントリのみを含む Set に追加することで、通過するすべてのノードを訪問済みとして「マーク」するのです。
このようにノードを「訪問済み」にすることで、もしそのノードに再び遭遇した場合、ループに陥ってしまうのです。無限の計算パワーと時間がループのために浪費され、エーテルに紛れ込んでいるのだ。
疑似コード
以上のような手順で、DFSを疑似コードでまとめることができます。
DFS(G, u):
# Input processing
u.visited = true
for each v in G.adj[u]:
if !v.visited:
DFS(G, v)
# Output processing
グラフ探索の目的に応じて、入出力処理を行う。DFSの入力処理は、カレントノードがターゲットノードと等しいかどうかをチェックする。
このように考えると、このアルゴリズムがいかにシンプルで有用であるかがわかると思う。
深層優先探索 – 実装
DFSアルゴリズム自体の実装に入る前に、まず考えなければならないのは、グラフをどのように実装するかということです。このシリーズの他の記事と同様に、かなり基本的な Graph クラスを使用して実装することにしました。このクラスには、グラフ表現と、グラフを操作するために必要ないくつかのメソッドが含まれています。
class Graph:
# Constructor
def __init__(self, num_of_nodes, directed=True):
self.m_num_of_nodes = num_of_nodes
self.m_nodes = range(self.m_num_of_nodes)
# Directed or Undirected
self.m_directed = directed
# Graph representation - Adjacency list
# We use a dictionary to implement an adjacency list
self.m_adj_list = {node: set() for node in self.m_nodes}
# Add edge to the graph
def add_edge(self, node1, node2, weight=1):
self.m_adj_list[node1].add((node2, weight))
if not self.m_directed:
self.m_adj_list[node2].add((node1, weight))
# Print the graph representation
def print_adj_list(self):
for key in self.m_adj_list.keys():
print("node", key, ": ", self.m_adj_list[key])
Graphクラスがどのように動作するかを簡単に説明します。__init__() メソッドはコンストラクタを定義しています。コンストラクタは、ノードの数、ノードの集合、そしてグラフの表現から構成される。この場合、グラフは隣接リスト、つまりグラフの各ノードを1つのキーとする Python 辞書で表現されます。各ノード（キー）には、隣接するノードのセットが割り当てられます。
注：隣接リストは、コードにおけるグラフ表現の一種で、各ノードを表すキーと、キーノードにエッジで接続されたノードを含む各ノードの値の集合から構成されます。
このために辞書を使うのが Python で素早くグラフを表現する最も簡単な方法ですが、代わりに Node クラスを独自に定義して Graph インスタンスに追加することも可能です。
その名前が示すように、 add_edge() メソッドはグラフ表現にエッジを追加するために使用されます。各エッジは通常の隣接リストと同じように表現されます。例えば、エッジ 1-2 は、隣接リストのノード 1 の隣接ノードとして 2 を追加することで表現される。さらに、我々の実装では、任意のエッジに重みを割り当てることができる。
最後に、グラフ表現を表示するメソッド – print_adj_list() を作成した。
これで、DFSアルゴリズムを Graph クラスに実装することができました。深さ優先探索の実装は、それがいかに自然なペアであるかを考えると、コード上では通常再帰的ですが、非再帰的に実装することも簡単にできます。ここでは、再帰的な方法を使用することにします。
def dfs(self, start, target, path = [], visited = set()):
path.append(start)
visited.add(start)
if start == target:
return path
for (neighbour, weight) in self.m_adj_list[start]:
if neighbour not in visited:
result = self.dfs(neighbour, target, path, visited)
if result is not None:
return result
path.pop()
return None
開始ノードを探索パスの最初に追加し、それを visited ノードの集合に追加することで訪問済みであることをマークします。次に、まだ訪問していない開始ノードの近傍ノードを走査し、それぞれのノードに対して再帰的に関数を呼び出します。再帰的に呼び出すと、1つの「枝」に沿ってできる限り深く進むことになります。
そして、その結果への参照を保存する。関数が None を返した場合、それは目的のノードがこのブランチで見つからなかったことを意味し、別のブランチを試す必要があります。もし、再帰呼び出しが None を返さなかった場合は、目的のノードが見つかったということなので、その探索パスを結果として返します。
最後に、もし for ループの外に出たとしたら、それは現在のノードの近傍の枝をすべて訪れ、そのどれもが目的のノードにつながらないことを意味します。そこで、カレントノードをパスから外し、結果として None を返します。