アルゴリズム

[Python] 横形探索(幅優先探索/BFS)を実装する方法

2025-01-18更新日: 2025-01-18

横形探索(幅優先探索、BFS)は、グラフやツリーの探索アルゴリズムの一つで、最短経路を見つける際に有効です。

PythonでBFSを実装するには、通常キューcollections.dequeを使用します。

まず、探索の開始点をキューに追加し、キューが空になるまで以下の手順を繰り返します。

目次から探す

幅優先探索(BFS)とは
BFSのアルゴリズムの流れ
PythonでのBFS実装方法
BFSの応用例
BFS実装時の注意点
BFSの発展的な話題
まとめ

幅優先探索(BFS)とは

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

このアルゴリズムは、スタートノードから始めて、隣接するノードをすべて訪問し、その後に次のレベルのノードを訪問するという方法で進行します。

BFSは、最短経路を見つけるのに適しており、特に無向グラフや重みのないグラフにおいて効果的です。

キューを使用して訪問するノードを管理し、訪問済みのノードを記録することで、無限ループを防ぎます。

BFSは、さまざまな応用があり、特にネットワークの探索や最短経路問題において重要な役割を果たします。

BFSのアルゴリズムの流れ

BFSの基本的な手順

幅優先探索(BFS)の基本的な手順は以下の通りです。

スタートノードをキューに追加し、訪問済みとしてマークする。
キューが空でない限り、以下の操作を繰り返す。

キューの先頭からノードを取り出す。
そのノードの隣接ノードをすべて確認する。
隣接ノードが未訪問であれば、キューに追加し、訪問済みとしてマークする。

この手順を繰り返すことで、すべてのノードを探索することができます。

キューを使った探索の仕組み

BFSでは、探索の順序を管理するためにキューを使用します。

キューはFIFO(先入れ先出し)構造であり、最初に追加されたノードが最初に取り出されます。

これにより、スタートノードから近いノードを優先的に探索することができます。

具体的には、以下のようにキューを操作します。

ノードを追加する際は、enqueue操作を使用。
ノードを取り出す際は、dequeue操作を使用。

この仕組みにより、BFSはレベルごとにノードを探索することが可能になります。

訪問済みノードの管理方法

BFSでは、訪問済みノードを管理するために、通常はセットやリストを使用します。

訪問済みのノードを記録することで、同じノードを再度訪問することを防ぎ、無限ループを避けることができます。

具体的な管理方法は以下の通りです。

新しいノードを訪問する際に、訪問済みリストに追加。
隣接ノードを確認する際に、訪問済みリストに存在しないかをチェック。

この管理方法により、効率的にノードを探索することができます。

BFSの計算量と空間計算量

BFSの計算量は、グラフのノード数を $V$ 、エッジ数を $E$ とした場合、以下のように表されます。

時間計算量: $O (V + E)$

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

空間計算量: $O (V)$

訪問済みノードの管理やキューのサイズが最大でノード数に依存するため、最悪の場合はノード数に比例します。

このように、BFSは効率的にグラフを探索することができるアルゴリズムです。

PythonでのBFS実装方法

Pythonでのキューの使い方

Pythonでは、キューを実装するためにcollectionsモジュールのdequeを使用するのが一般的です。

dequeは両端キューであり、効率的に要素の追加と削除が行えます。

以下は、dequeを使ったキューの基本的な操作の例です。

from collections import deque
# キューの初期化
queue = deque()
# 要素の追加
queue.append('A')
queue.append('B')
# 要素の取り出し
first_element = queue.popleft()  # 'A'が取り出される

このように、appendメソッドで要素を追加し、popleftメソッドで先頭の要素を取り出すことができます。

BFSの基本的な実装例

以下は、BFSを用いてグラフを探索する基本的な実装例です。

from collections import deque
def bfs(graph, start):
    visited = set()  # 訪問済みノードのセット
    queue = deque([start])  # スタートノードをキューに追加
    while queue:
        node = queue.popleft()  # キューからノードを取り出す
        if node not in visited:
            print(node)  # ノードを訪問
            visited.add(node)  # 訪問済みとしてマーク
            queue.extend(graph[node])  # 隣接ノードをキューに追加
# グラフの例
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
bfs(graph, 'A')

A
B
C
D
E
F

このコードでは、スタートノードからBFSを実行し、訪問したノードを順に出力します。

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

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

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

無向グラフでのBFS実装

無向グラフにおけるBFSの実装は、基本的なBFSの実装と同様ですが、隣接リストの構造を無向にする必要があります。

以下はその例です。

from collections import deque
def bfs_undirected(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node)
            visited.add(node)
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)
# 無向グラフの例
undirected_graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
bfs_undirected(undirected_graph, 'A')

A
B
C
D
E
F

有向グラフでのBFS実装

有向グラフの場合も、基本的なBFSの実装を使用しますが、隣接リストは有向に設定します。

以下はその例です。

from collections import deque
def bfs_directed(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node)
            visited.add(node)
            queue.extend(graph[node])  # 隣接ノードを追加
# 有向グラフの例
directed_graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
bfs_directed(directed_graph, 'A')

A
B
C
D
E
F

迷路探索におけるBFSの実装

迷路探索においてBFSを使用することで、最短経路を見つけることができます。

以下は、迷路を2次元リストで表現し、BFSを用いて出口を探す例です。

from collections import deque
def bfs_maze(maze, start, end):
    rows, cols = len(maze), len(maze[0])
    visited = set()
    queue = deque([start])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右、下、左、上
    while queue:
        x, y = queue.popleft()
        if (x, y) == end:
            print("出口に到達しました。")
            return
        if (x, y) not in visited:
            visited.add((x, y))
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == 0 and (nx, ny) not in visited:
                    queue.append((nx, ny))
    print("出口には到達できませんでした。")
# 迷路の例 (0: 通行可能, 1: 通行不可)
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 0, 1, 0]
]
bfs_maze(maze, (0, 0), (4, 4))

出口に到達しました。

このように、BFSを用いることで迷路の出口を効率的に探索することができます。

BFSの応用例

最短経路問題への応用

BFSは、無向グラフや重みのないグラフにおける最短経路問題を解決するのに非常に効果的です。

スタートノードから各ノードへの距離をレベルとして考え、最初に訪問したノードが最短経路であることが保証されます。

例えば、迷路のような構造で、各セルがノード、隣接するセルがエッジと考えると、BFSを用いてスタート地点からゴール地点までの最短経路を見つけることができます。

二部グラフ判定への応用

二部グラフとは、グラフのノードを2つのグループに分け、同じグループ内のノード同士が接続されていないグラフのことです。

BFSを用いることで、グラフを2色に塗り分けることができ、隣接するノードが異なる色になるかを確認することで、二部グラフであるかどうかを判定できます。

具体的には、BFSを実行しながら、訪問したノードに色を付けていき、隣接ノードが同じ色であれば二部グラフではないと判断します。

トポロジカルソートへの応用

トポロジカルソートは、有向非巡回グラフ(DAG)のノードを線形に並べる手法です。

BFSを用いたKahnのアルゴリズムを使うことで、トポロジカルソートを実現できます。

このアルゴリズムでは、入次数が0のノードをキューに追加し、キューからノードを取り出すたびに、そのノードに接続されているエッジを削除し、入次数が0になったノードを再度キューに追加します。

これを繰り返すことで、ノードをトポロジカルに並べることができます。

Webクローラーの実装におけるBFS

Webクローラーは、インターネット上のページを探索し、情報を収集するプログラムです。

BFSを用いることで、特定のURLから始めて、そのページにリンクされている他のページを順に訪問することができます。

クローラーは、訪問したページを記録し、重複を避けるために訪問済みのURLを管理します。

これにより、効率的にウェブ全体を探索し、情報を収集することが可能になります。

ソーシャルネットワーク分析におけるBFS

ソーシャルネットワークにおいて、BFSはユーザー間の関係を分析するために使用されます。

例えば、特定のユーザーから始めて、そのユーザーの友人や友人の友人を探索することで、ネットワークの構造を理解することができます。

また、BFSを用いることで、特定のユーザーとの最短距離を計算したり、特定の条件を満たすユーザーを見つけたりすることができます。

これにより、ソーシャルネットワークのダイナミクスを把握し、マーケティング戦略やコミュニティの形成に役立てることができます。

BFS実装時の注意点

無限ループを防ぐための工夫

BFSを実装する際には、無限ループを防ぐために訪問済みノードを適切に管理することが重要です。

訪問済みノードを記録するために、セットやリストを使用し、ノードを訪問する前にそのノードが既に訪問済みかどうかを確認します。

これにより、同じノードを何度も訪問することを防ぎ、無限ループを回避できます。

以下は、訪問済みノードを管理するための基本的な方法です。

visited = set()  # 訪問済みノードのセット
if node not in visited:
    visited.add(node)  # 訪問済みとしてマーク

メモリ使用量の最適化

BFSは、キューや訪問済みノードの管理にメモリを使用します。

特に大規模なグラフを扱う場合、メモリ使用量が問題になることがあります。

メモリ使用量を最適化するためには、以下の点に注意します。

訪問済みノードの管理: 訪問済みノードをセットで管理することで、重複を避けつつメモリを効率的に使用できます。
キューのサイズ: キューに追加するノードを必要最小限に抑えるため、隣接ノードの訪問を行う際に、未訪問のノードのみを追加します。
データ構造の選択: グラフの表現方法(隣接リストや隣接行列)を選ぶ際、メモリ効率を考慮して適切なデータ構造を選択します。

大規模グラフでのBFSの効率化

大規模なグラフを扱う場合、BFSの効率を向上させるために以下の工夫が考えられます。

部分グラフの探索: 全体のグラフを一度に探索するのではなく、部分グラフを対象にして探索を行うことで、メモリと時間の効率を向上させます。
並列処理: BFSの各レベルを並列に処理することで、探索速度を向上させることができます。

Pythonではmultiprocessingモジュールを使用して並列処理を実現できます。

ヒューリスティックの導入: 特定の条件に基づいてノードの探索順序を変更することで、無駄な探索を減らし、効率を向上させることができます。

BFSとDFSの使い分け

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

使い分ける際には、以下のポイントを考慮します。

最短経路の探索: BFSは無向グラフや重みのないグラフにおける最短経路を見つけるのに適しています。

一方、DFSは最短経路を保証しませんが、特定の条件を満たす解を見つけるのに有効です。

メモリ使用量: BFSはキューを使用するため、メモリ使用量が多くなることがあります。

DFSはスタックを使用するため、メモリ使用量が少なくなることが多いです。

探索の深さ: DFSは深いノードを優先的に探索するため、特定の深さにある解を見つけるのに適しています。

BFSはレベルごとに探索を行うため、広範囲にわたる探索が必要な場合に有効です。

このように、BFSとDFSはそれぞれの特性を理解し、適切な場面で使い分けることが重要です。

BFSの発展的な話題

双方向BFSの実装

双方向BFSは、スタートノードからゴールノードに向かう探索と、ゴールノードからスタートノードに向かう探索を同時に行う手法です。

この方法により、探索の範囲を大幅に削減し、効率的に最短経路を見つけることができます。

以下は、双方向BFSの基本的な実装例です。

from collections import deque
def bidirectional_bfs(graph, start, goal):
    if start == goal:
        return [start]
    visited_start = set([start])
    visited_goal = set([goal])
    queue_start = deque([start])
    queue_goal = deque([goal])
    while queue_start and queue_goal:
        # スタートからの探索
        if queue_start:
            node_start = queue_start.popleft()
            if node_start in visited_goal:
                return reconstruct_path(node_start, visited_start, visited_goal)
            for neighbor in graph[node_start]:
                if neighbor not in visited_start:
                    visited_start.add(neighbor)
                    queue_start.append(neighbor)
        # ゴールからの探索
        if queue_goal:
            node_goal = queue_goal.popleft()
            if node_goal in visited_start:
                return reconstruct_path(node_goal, visited_goal, visited_start)
            for neighbor in graph[node_goal]:
                if neighbor not in visited_goal:
                    visited_goal.add(neighbor)
                    queue_goal.append(neighbor)
    return None  # 経路が見つからなかった場合
def reconstruct_path(meeting_node, visited_from_start, visited_from_goal):
    # 経路を再構築するロジックを実装
    return []  # 実際の経路を返す
# グラフの例
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
path = bidirectional_bfs(graph, 'A', 'F')
print(path)

多始点BFSの実装

多始点BFSは、複数のスタートノードから同時に探索を行う手法です。

この方法は、特定の条件を満たすノードを効率的に見つけるのに役立ちます。

以下は、多始点BFSの実装例です。

from collections import deque
def multi_source_bfs(graph, starts):
    visited = set(starts)  # 複数のスタートノードを訪問済みとしてマーク
    queue = deque(starts)
    while queue:
        node = queue.popleft()
        print(node)  # ノードを訪問
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
# グラフの例
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'E'],
    'D': ['B'],
    'E': ['C']
}
multi_source_bfs(graph, ['A', 'C'])