Python WebAcademy

学習モード

グラフ理論とグラフアルゴリズム

Section 5 / 12

再帰的DFSと非再帰的DFS

深さ優先探索（DFS）は、グラフや木構造を探索するためのアルゴリズムです。DFSには再帰的な実装と非再帰的な実装の2つの方法があります。ここでは、それぞれの実装方法を学び、理解を深めていきましょう。

再帰的DFSの実装

再帰的DFSは、関数が自分自身を呼び出すことで、ノードを探索していく方法です。以下に、再帰的DFSのサンプルコードを示します。

# 再帰的DFSの実装
def recursive_dfs(graph, node, visited):
    if node not in visited:
        print(node)  # 現在のノードを訪問
        visited.add(node)  # 訪問済みノードに追加
        for neighbor in graph[node]:  # 隣接ノードを再帰的に訪問
            recursive_dfs(graph, neighbor, visited)

# グラフの定義（隣接リスト形式）
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# DFSを実行
visited_nodes = set()
recursive_dfs(graph, 'A', visited_nodes)

コードの解説

  1. 関数定義: recursive_dfs関数は、探索対象のグラフ、現在のノード、訪問済みノードの集合を引数に取ります。
  2. 訪問チェック: ノードが訪問済みでない場合、ノードを出力し、訪問済みノードに追加します。
  3. 再帰呼び出し: 現在のノードの隣接ノードをすべて再帰的に訪問します。
  4. グラフの定義: graphは、隣接リスト形式でグラフを表現しています。
  5. DFSの実行: 最後に、recursive_dfs関数を呼び出して探索を開始します。

非再帰的DFSの実装

非再帰的DFSは、スタックを使用してノードを管理し、明示的に再帰を行わずに探索を進める方法です。以下に、非再帰的DFSのサンプルコードを示します。

# 非再帰的DFSの実装
def iterative_dfs(graph, start):
    visited = set()  # 訪問済みノードの集合
    stack = [start]  # スタックに開始ノードを追加

    while stack:  # スタックが空でない限り繰り返す
        node = stack.pop()  # スタックからノードを取り出す
        if node not in visited:
            print(node)  # 現在のノードを訪問
            visited.add(node)  # 訪問済みノードに追加
            # 隣接ノードをスタックに追加（逆順にすることで正しい順序で訪問）
            stack.extend(reversed(graph[node]))

# DFSを実行
iterative_dfs(graph, 'A')

コードの解説

  1. 関数定義: iterative_dfs関数は、探索対象のグラフと開始ノードを引数に取ります。
  2. スタックの初期化: 開始ノードをスタックに追加します。
  3. 探索ループ: スタックが空でない限り、ノードを取り出して訪問します。
  4. 訪問チェック: ノードが訪問済みでない場合、ノードを出力し、訪問済みノードに追加します。
  5. 隣接ノードの追加: 現在のノードの隣接ノードをスタックに追加します。このとき、逆順に追加することで、元の順序で訪問されるようにします。

まとめ

再帰的DFSと非再帰的DFSは、どちらも深さ優先探索を実現するための方法ですが、実装のアプローチが異なります。再帰的DFSはシンプルで直感的ですが、スタックオーバーフローのリスクがあります。一方、非再帰的DFSはスタックを使用するため、より大きなグラフに対しても安定して動作します。

これらのDFSの違いを理解することで、さまざまな問題に対して適切なアルゴリズムを選択できるようになります。実際にコードを動かしてみて、動作を確認してみましょう。

前に戻る