MENU
  1. ホーム
  2. Python
  3. アルゴリズム
  4. [Python] 深さ優先探索(DFS)で目的のノードを探索する方法

[Python] 深さ優先探索(DFS)で目的のノードを探索する方法

深さ優先探索(DFS)は、グラフや木構造において、スタートノードから始めて、可能な限り深く探索していくアルゴリズムです。

Pythonでは、再帰やスタックを使って実装できます。

再帰的な実装では、まず現在のノードを訪問し、次にそのノードに隣接する未訪問のノードに対して再帰的に探索を行います。

スタックを使う場合は、スタックにノードを追加し、取り出して探索を進めます。

DFSは、目的のノードが深い位置にある場合に効率的です。

この記事でわかること
  • 深さ優先探索(DFS)の基本
  • PythonでのDFSの実装方法
  • DFSの応用例とその利点
  • DFSのパフォーマンスと最適化手法
  • 探索アルゴリズムの選択基準

目次から探す

深さ優先探索(DFS)とは

深さ優先探索(DFS)は、グラフや木構造を探索するためのアルゴリズムの一つです。

この手法は、あるノードから出発し、可能な限り深く探索を進めていくことが特徴です。

探索中に行き止まりに達した場合は、バックトラックして別の経路を試みます。

DFSは、再帰的なアプローチやスタックを用いて実装されることが多く、特に連結成分の探索や迷路の解法、トポロジカルソートなど、さまざまな応用が存在します。

DFSは、探索の過程で訪問したノードを記録することで、無限ループを防ぎ、効率的に目的のノードを見つけることができます。

PythonでのDFSの実装方法

再帰を使ったDFSの実装

再帰を用いた深さ優先探索は、シンプルで直感的な実装が可能です。

以下のサンプルコードでは、再帰的にノードを訪問し、目的のノードを探索します。

def dfs_recursive(graph, node, visited):
    if node not in visited:
        print(node)  # ノードを訪問
        visited.add(node)  # 訪問済みリストに追加
        for neighbor in graph[node]:  # 隣接ノードを探索
            dfs_recursive(graph, neighbor, visited)
# グラフの定義
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
visited_nodes = set()
dfs_recursive(graph, 'A', visited_nodes)
A
B
D
E
F
C

再帰を使用することで、コードが簡潔になり、ノードの探索が自然に表現されます。

スタックを使ったDFSの実装

スタックを用いたDFSは、明示的にスタックを管理することで、再帰を使用せずに探索を行います。

以下のサンプルコードでは、スタックを使ってノードを訪問します。

def dfs_stack(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]))  # 隣接ノードをスタックに追加
# グラフの定義
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
dfs_stack(graph, 'A')
A
B
D
E
F
C

スタックを使用することで、再帰の深さ制限を気にせずに探索を行うことができます。

グラフの表現方法(隣接リスト、隣接行列)

グラフを表現する方法には主に以下の2つがあります。

スクロールできます
表現方法説明
隣接リスト各ノードに対して、そのノードに隣接するノードのリストを持つ。メモリ効率が良い。
隣接行列ノード間の接続を行列で表現。接続がある場合は1、ない場合は0を格納。計算が簡単だが、メモリを多く消費する。

ノードの訪問管理(訪問済みリストの使用)

DFSでは、ノードの訪問管理が重要です。

訪問済みリストを使用することで、同じノードを再度訪問することを防ぎ、無限ループを回避します。

訪問済みリストは、セットやリストを用いて実装され、探索中に訪問したノードを記録します。

これにより、効率的に目的のノードを見つけることができます。

DFSで目的のノードを探索する手順

探索の開始点を決める

深さ優先探索(DFS)を行う際には、まず探索を開始するノードを決定します。

このノードは、グラフの任意のノードで構いませんが、通常は特定の条件に基づいて選ばれます。

例えば、特定のデータを持つノードや、最初に訪問するノードとして設定されることが一般的です。

以下のサンプルコードでは、ノード’A’を開始点として設定しています。

start_node = 'A'  # 探索の開始点

再帰的に隣接ノードを探索する

開始点が決まったら、再帰的に隣接ノードを探索します。

訪問したノードは訪問済みリストに追加し、隣接ノードに対して再帰的にDFSを呼び出します。

以下のサンプルコードでは、再帰的に隣接ノードを探索する様子を示しています。

def dfs_recursive(graph, node, visited):
    if node not in visited:
        print(node)  # ノードを訪問
        visited.add(node)  # 訪問済みリストに追加
        for neighbor in graph[node]:  # 隣接ノードを探索
            dfs_recursive(graph, neighbor, visited)
# グラフの定義と探索の開始
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
start_node = 'A'  # 探索の開始点
visited_nodes = set()
dfs_recursive(graph, start_node, visited_nodes)

目的のノードに到達した場合の処理

目的のノードに到達した場合、特定の処理を行います。

例えば、目的のノードを見つけたことを示すメッセージを表示したり、探索を終了したりします。

以下のサンプルコードでは、目的のノードが見つかった場合の処理を示しています。

def dfs_find_target(graph, node, visited, target):
    if node not in visited:
        visited.add(node)  # 訪問済みリストに追加
        if node == target:  # 目的のノードに到達した場合
            print(f"目的のノード '{target}' を見つけました！")
            return True  # 探索を終了
        for neighbor in graph[node]:  # 隣接ノードを探索
            if dfs_find_target(graph, neighbor, visited, target):
                return aTrue  # 目的のノードが見つかった場合
# グラフの定義と探索の開始
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
# 目的のノードを設定
start_node = 'A'
target_node = 'E'
visited_nodes = set()
dfs_find_target(graph, start_node, visited_nodes, target_node)
目的のノード 'E' を見つけました！

目的のノードが見つからなかった場合の処理

目的のノードが見つからなかった場合、探索を続けるか、探索を終了するかの処理を行います。

通常は、全てのノードを探索した後に目的のノードが見つからなかったことを示すメッセージを表示します。

以下のサンプルコードでは、目的のノードが見つからなかった場合の処理を示しています。

def dfs_find_target_with_not_found(graph, node, visited, target):
    if node not in visited:
        visited.add(node)  # 訪問済みリストに追加
        if node == target:  # 目的のノードに到達した場合
            print(f"目的のノード '{target}' を見つけました！")
            return True  # 探索を終了
        for neighbor in graph[node]:  # 隣接ノードを探索
            if dfs_find_target_with_not_found(graph, neighbor, visited, target):
                return True  # 目的のノードが見つかった場合
    return False  # 目的のノードが見つからなかった場合
# グラフの定義と探索の開始
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
# 目的のノードを設定
start_node = 'A'
# 目的のノードを設定(存在しないノード)
target_node_not_found = 'G'
visited_nodes = set()
found = dfs_find_target_with_not_found(graph, start_node, visited_nodes, target_node_not_found)
if not found:
    print(f"目的のノード '{target_node_not_found}' は見つかりませんでした。")
目的のノード 'G' は見つかりませんでした。

このように、DFSを用いて目的のノードを探索する際には、開始点の設定から隣接ノードの探索、目的のノードに到達した場合や見つからなかった場合の処理を適切に行うことが重要です。

DFSの応用例

迷路の解法におけるDFSの利用

深さ優先探索(DFS)は、迷路の解法において非常に有効な手法です。

迷路をグラフとして表現し、スタート地点からゴール地点までの経路を探索します。

DFSを用いることで、すべての可能な経路を試し、最終的にゴールに到達する経路を見つけることができます。

以下のサンプルコードでは、迷路を表現し、DFSを用いて解法を示しています。

def maze_dfs(maze, start, end, path=[], visited=None):
    if visited is None:
        visited = set()
    
    x, y = start
    if start == end:
        return path + [start]  # ゴールに到達した場合
    
    if not (0 <= x < len(maze) and 0 <= y < len(maze[0])):  # 範囲外チェック
        return None
    if maze[x][y] == 1:  # 壁の場合
        return None
    if start in visited:  # 既に訪問済みの場合
        return None
    
    visited.add(start)  # 訪問済みとしてマーク
    path = path + [start]  # 現在の経路を追加
    
    # 上下左右の隣接ノードを探索
    for move in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        next_pos = (x + move[0], y + move[1])
        result = maze_dfs(maze, next_pos, end, path, visited)
        if result is not None:
            return result  # ゴールに到達した場合
    
    return None  # ゴールに到達できなかった場合

# 迷路の定義(0: 通路, 1: 壁)
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 0, 1, 0]
]
start = (0, 0)  # スタート地点
end = (4, 4)    # ゴール地点
path = maze_dfs(maze, start, end)
print("迷路の解法:", path)
迷路の解法: [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (3, 3), (3, 4), (4, 4)]

グラフの連結成分の探索

DFSは、グラフの連結成分を探索するのにも利用されます。

連結成分とは、グラフの中で互いに到達可能なノードの集合を指します。

DFSを用いることで、各ノードを訪問し、どのノードが同じ連結成分に属するかを特定できます。

以下のサンプルコードでは、連結成分を探索する様子を示しています。

def dfs_connected_components(graph, node, visited):
    visited.add(node)  # 訪問済みリストに追加
    for neighbor in graph[node]:  # 隣接ノードを探索
        if neighbor not in visited:
            dfs_connected_components(graph, neighbor, visited)
# グラフの定義
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B'],
    'E': ['F'],
    'F': ['E']
}
visited = set()
components = []
for node in graph:
    if node not in visited:
        component = set()
        dfs_connected_components(graph, node, component)
        components.append(component)  # 連結成分を追加
print("連結成分:", components)
連結成分: [{'C', 'A', 'D', 'B'}, {'A', 'D', 'B', 'C'}, {'D', 'A', 'C', 'B'}, {'A', 'B', 'D', 'C'}, {'E', 'F'}, {'E', 'F'}]

トポロジカルソートにおけるDFSの利用

トポロジカルソートは、有向非巡回グラフ(DAG)のノードを順序付ける手法で、DFSを用いて実装されます。

DFSを用いることで、各ノードを訪問し、訪問が完了したノードをスタックに追加します。

最終的にスタックを逆順にすることで、トポロジカルソートを得ることができます。

以下のサンプルコードでは、トポロジカルソートの実装を示しています。

def topological_sort_dfs(graph):
    visited = set()
    stack = []
    def dfs(node):
        visited.add(node)  # 訪問済みリストに追加
        for neighbor in graph[node]:  # 隣接ノードを探索
            if neighbor not in visited:
                dfs(neighbor)
        stack.append(node)  # 訪問完了したノードをスタックに追加
    for node in graph:
        if node not in visited:
            dfs(node)
    return stack[::-1]  # スタックを逆順にして返す
# グラフの定義(DAG)
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}
sorted_nodes = topological_sort_dfs(graph)
print("トポロジカルソート:", sorted_nodes)
トポロジカルソート: ['A', 'C', 'B', 'D']

木構造の探索におけるDFSの利用

DFSは、木構造の探索にも広く利用されます。

木構造は、親子関係を持つノードの集合であり、DFSを用いることで、特定のノードを効率的に探索できます。

以下のサンプルコードでは、木構造を表現し、DFSを用いてノードを探索する様子を示しています。

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []  # 子ノードのリスト
def dfs_tree(node):
    if node is not None:
        print(node.value)  # ノードを訪問
        for child in node.children:  # 子ノードを探索
            dfs_tree(child)
# 木構造の定義
root = TreeNode('A')
child_b = TreeNode('B')
child_c = TreeNode('C')
root.children.append(child_b)
root.children.append(child_c)
child_b.children.append(TreeNode('D'))
child_b.children.append(TreeNode('E'))
child_c.children.append(TreeNode('F'))
print("木構造のDFS探索:")
dfs_tree(root)
木構造のDFS探索:
A
B
D
E
C
F

このように、DFSはさまざまな応用例があり、迷路の解法やグラフの連結成分の探索、トポロジカルソート、木構造の探索など、多岐にわたって利用されています。

DFSのパフォーマンスと最適化

計算量と空間計算量

深さ優先探索(DFS)の計算量は、探索するグラフのノード数とエッジ数に依存します。

一般的に、DFSの計算量は以下のように表されます。

  • 計算量: \(O(V + E)\)
  • \(V\): ノードの数
  • \(E\): エッジの数

DFSは、すべてのノードとエッジを一度ずつ訪問するため、計算量はノード数とエッジ数の合計に比例します。

  • 空間計算量: \(O(V)\)
  • 訪問済みリストやスタック(再帰の場合はコールスタック)を使用するため、最悪の場合、空間計算量はノード数に比例します。

特に、深い木構造やグラフの場合、空間計算量が大きくなることがあります。

再帰の深さ制限とスタックオーバーフローの回避

再帰を使用したDFSでは、再帰の深さがPythonのデフォルトの制限を超えると、スタックオーバーフローが発生する可能性があります。

Pythonのデフォルトの再帰制限は1000回程度であり、深いグラフや木構造を探索する際には注意が必要です。

これを回避するためには、以下の方法があります。

  • 再帰の深さ制限を変更する: sysモジュールを使用して、再帰の深さ制限を変更できます。
import sys
sys.setrecursionlimit(2000)  # 再帰の深さ制限を2000に設定
  • スタックを使用する: 再帰の代わりに明示的なスタックを使用することで、スタックオーバーフローを回避できます。

スタックを使用することで、再帰の深さに依存せずにDFSを実行できます。

メモ化による効率化

DFSを使用する際に、同じノードを何度も訪問することがある場合、メモ化を利用することで効率化が可能です。

メモ化は、計算結果をキャッシュして再利用する手法で、特に重複する計算が多い場合に効果的です。

以下のサンプルコードでは、メモ化を用いたDFSの実装を示しています。

def dfs_memoization(graph, node, visited, memo):
    if node in memo:  # メモに結果がある場合
        return memo[node]
    if node in visited:  # 訪問済みの場合
        return None
    visited.add(node)  # 訪問済みリストに追加
    result = [node]  # 結果を初期化
    for neighbor in graph[node]:  # 隣接ノードを探索
        sub_result = dfs_memoization(graph, neighbor, visited, memo)
        if sub_result is not None:
            result.extend(sub_result)  # 結果を追加
    memo[node] = result  # メモに結果を保存
    return result
# グラフの定義
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}
visited_nodes = set()
memo = {}
result = dfs_memoization(graph, 'A', visited_nodes, memo)
print("メモ化によるDFSの結果:", result)
メモ化によるDFSの結果: ['A', 'B', 'D', 'C', 'D']

グラフのサイズが大きい場合の工夫

グラフのサイズが大きい場合、DFSのパフォーマンスが低下することがあります。

以下の工夫を行うことで、効率的に探索を行うことができます。

  • グラフの表現を最適化する: 隣接リストを使用することで、メモリの使用量を削減し、探索を効率化できます。

隣接行列は、ノード数が多い場合にメモリを大量に消費するため、注意が必要です。

  • 部分的な探索を行う: 大きなグラフを一度に探索するのではなく、部分的に探索を行うことで、メモリの使用量を抑えることができます。

特定の条件に基づいて探索を制限することも有効です。

  • 非再帰的なアプローチを使用する: スタックを使用した非再帰的なDFSを実装することで、再帰の深さ制限を気にせずに探索を行うことができます。

これにより、大きなグラフでも安定して動作します。

これらの最適化手法を用いることで、DFSのパフォーマンスを向上させ、より効率的な探索を実現することができます。

よくある質問

DFSとBFSはどちらを使うべき？

DFS(深さ優先探索)とBFS(幅優先探索)は、それぞれ異なる特性を持つ探索アルゴリズムです。

どちらを使用するかは、問題の性質によります。

以下のポイントを考慮してください。

  • DFSを使うべき場合:
  • 解が深い場所にある場合(例: 迷路の解法やパズルの探索)
  • メモリ使用量を抑えたい場合(スタックを使用するため、メモリ効率が良い)
  • トポロジカルソートや連結成分の探索など、特定のグラフ構造に対して有効な場合
  • BFSを使うべき場合:
  • 最短経路を見つけたい場合(例: グラフの最短経路問題)
  • 解が浅い場所にある場合(例: 階層的なデータ構造の探索)
  • グラフの全体を均等に探索したい場合

再帰とスタックのどちらが効率的？

再帰とスタックを用いたDFSの効率性は、状況によって異なります。

  • 再帰の利点:
  • コードがシンプルで直感的に理解しやすい
  • 再帰的な構造が自然に表現できる
  • スタックの利点:
  • 再帰の深さ制限を気にせずに探索できる
  • 大きなグラフや深い木構造を扱う際に、スタックオーバーフローを回避できる

一般的には、再帰が簡潔であるため小規模な問題には適していますが、大規模な問題や深い構造を扱う場合はスタックを使用する方が安全です。

DFSで無限ループに陥る原因は？

DFSで無限ループに陥る主な原因は、訪問済みノードの管理が不十分であることです。

具体的には以下のようなケースがあります。

  • 訪問済みリストを使用しない: ノードを訪問したかどうかを記録しないと、同じノードを何度も訪問し続けることになります。

これにより、無限ループが発生します。

  • 不適切なグラフの表現: グラフが循環している場合、訪問済みリストを適切に管理しないと、無限に同じノードを訪問することになります。
  • 再帰の深さ制限を超える: 再帰を使用している場合、深い構造を持つグラフでスタックオーバーフローが発生し、意図しない動作を引き起こすことがあります。

無限ループを防ぐためには、訪問済みリストを適切に使用し、ノードの訪問状況を管理することが重要です。

また、グラフの構造を理解し、適切なアルゴリズムを選択することも大切です。

まとめ

この記事では、深さ優先探索(DFS)の基本的な概念から実装方法、応用例、パフォーマンスの最適化に至るまで、幅広く解説しました。

DFSは、特にグラフや木構造の探索において非常に有用なアルゴリズムであり、さまざまな問題に適用可能です。

これを機に、DFSを実際のプログラミングやアルゴリズムの学習に活用してみてください。

目次に戻る

当サイトはリンクフリーです。出典元を明記していただければ、ご自由に引用していただいて構いません。

C言語
C++
Python
HTML
Java
HTTP

関連カテゴリーから探す

アルゴリズム
  • URLをコピーしました！

関連記事

目次から探す