Python WebAcademy

学習モード

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

Section 4 / 12

深さ優先探索（DFS）の実装と用途

深さ優先探索（DFS: Depth-First Search）は、グラフや木構造を探索するための基本的なアルゴリズムの一つです。DFSは、あるノードから始め、隣接するノードを訪問しながら可能な限り深く進んでいく手法です。すべてのノードを訪問するまで、再帰的またはスタックを使用して探索を続けます。

DFSの用途

DFSは以下のような多くの用途があります。

  • 経路探索：特定のノードへの経路を見つける。
  • 連結成分の検出：無向グラフにおける連結成分の数を数える。
  • トポロジカルソート：有向非巡回グラフ（DAG）のノードを順序付ける。
  • 迷路問題：迷路の解答を見つける。
  • パズル問題：解答があるかどうかを探す。

DFSの実装

DFSの実装は、再帰的アプローチと非再帰的アプローチの2つがあります。ここでは、両方の方法を示します。

再帰的DFSの実装

以下のコードは、再帰を使ったDFSの実装です。

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()

    visited.add(start)
    print(start)

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

    return visited

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

# DFSの実行
dfs_recursive(graph, 'A')

コードの解説

  1. dfs_recursive関数は、グラフ、開始ノード、および訪問済みノードの集合を引数とします。
  2. 訪問済みのノードを保持するために、visitedというセットを使用します。
  3. 現在のノードを訪問済みのセットに追加し、ノードを出力します。
  4. 隣接ノードに対して、訪問済みでない場合に再帰的にDFSを呼び出します。

非再帰的DFSの実装

次に、非再帰的なDFSを実装します。この方法では、スタックを使用します。

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()

        if vertex not in visited:
            visited.add(vertex)
            print(vertex)
            stack.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)

    return visited

# DFSの実行
dfs_iterative(graph, 'A')

コードの解説

  1. dfs_iterative関数は、グラフと開始ノードを引数とします。
  2. 訪問済みのノードを保持するために、visitedというセットと、探索するノードを保持するスタックを使用します。
  3. スタックが空でない限り、スタックの先頭からノードを取り出します。
  4. そのノードが未訪問であれば、訪問済みのセットに追加し、ノードを出力します。
  5. 隣接ノードをスタックに追加しますが、訪問済みでないノードのみを追加します。

まとめ

深さ優先探索（DFS）は、グラフや木構造を探索するための強力なアルゴリズムです。再帰的および非再帰的な方法で実装でき、さまざまな問題に応用可能です。 DFSを理解することで、より複雑なアルゴリズムや問題解決に進むための基礎を築くことができます。

前に戻る