DFS/BFS — 深さ優先探索 vs 幅優先探索

このトピックを修了すると

DFSとBFSがグラフを探索する方式の違いを理解し、問題の種類に応じてどちらを使用すべきかを判断できるようになります。

迷路から脱出するための2つの戦略

迷路に入りました。分岐点が現れます。2つの戦略があります。

戦略A: ある方向を選び、最後まで進みます。行き詰まったら、最後の分岐点に戻り、別の道を探します。一つの道を深く掘り進む方法です。

戦略B: 分岐点で、すべての方向に一歩ずつ進みます。次の分岐点でも、すべての方向に一歩ずつ。同心円のように広がっていく方法です。

戦略AはDFS（深さ優先探索）、戦略Bは**BFS（幅優先探索）**です。

DFS — 一つの道を進みきる

text

A
   / \
  B   C
 / \   \
D   E   F

Aから開始してDFSで探索すると：A → B → D → （行き詰まり、引き返す）→ E → （引き返す）→ C → F

ある分岐点を選ぶと、最後まで進みます。それ以上進めなくなったら、戻って（バックトラック）別の分岐点を探索します。

実装には**スタック（Stack）または再帰（Recursion）**を使用します。

python

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

再帰呼び出し自体がスタックのように動作します。関数が関数を呼び出すことで深くまで進み、returnすることで戻ります。

BFS — 近くのものからすべて

同じ木をBFSで探索すると：A → B → C → D → E → F

Aから1つ離れたB、Cを最初に訪問します。次に、2つ離れたD、E、Fを訪問します。距離が近い順に探索します。

実装には**キュー（Queue）**を使用します。

python

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

キューに入れた順に処理するため、近くのノードが最初に出てきます。

核心的な違い：スタック vs キュー

DFSとBFSのコードはほぼ同じです。違いは、次のノードをどのように管理するかだけです。

text

DFS：スタック（または再帰）→ 最後に挿入したものを最初に取り出す → 深さ方向
BFS：キュー → 最初に挿入したものを最初に取り出す → 幅方向

データ構造を1つ変えるだけで、探索の順序が完全に変わります。

いつ、どちらを使うか

DFSが適切な場合：

パスが存在するかどうかを確認する（存在する/存在しない）
すべてのケースを探索する必要がある場合（バックトラッキング）
迷路で出口を1つ見つければよい場合
メモリを少なく使用したい場合（現在のパスのみを保存）

BFSが適切な場合：

最短経路を見つける必要がある場合
近くのものから探索する必要がある場合
SNSで「友達の友達」を推薦
ネットワークで最も近いサーバーを見つける

最も重要な区別：最短距離が必要な場合はBFS、存在するかどうかを確認するだけであればDFS。

BFSは近くのノードから訪問するため、最初に到達したパスが最短経路です。DFSは深さ方向に進むため、最短経路を保証しません。

時間計算量

どちらも**O(V + E)**です。Vはノード数、Eはエッジ数です。すべてのノードを1回ずつ、すべてのエッジを1回ずつ確認します。探索の順序は異なりますが、全体の作業量は同じです。

空間計算量は異なります。DFSは、現在の探索パスの深さ分だけスタックを使用します。BFSは、同じレベルのノードをすべてキューに入れるため、幅の広いグラフではより多くのメモリを使用します。

核心

DFSは一つの方向を最後まで探索し、行き詰まったら引き返します。スタック/再帰を使用します。 BFSは近くのものからすべて探索します。キューを使用します。最短経路が必要な場合はBFS、存在するかどうかを確認するだけであればDFSが適切です。

BioPlayground

DFS/BFS — 深さ優先探索と幅優先探索