Pythonで幅優先探索（BFS）の仕組みを理解する

上長から、幅優先探索の第一引数に渡すデータを作成してほしいと依頼された。

しかし、その場ですぐに対応することができなかった。

エンジニアとしての実力が可視化された瞬間だった。

実力不足を痛感できる環境にいることを前向きに捉え、ここからスキルアップしていきたい。

手始めに、Pythonで幅優先探索を実装し、その処理の流れを一つずつ確認する。

幅優先探索（BFS）とは

幅優先探索（Breadth-First Search、BFS）は、グラフやツリー構造を探索するアルゴリズムの一つ。

スタート地点に近いノードから、横方向へ広がるように順番に探索していく。

主な特徴は次のとおり。

• 重みのないグラフでは、最短経路を求めるために利用できる
• スタート地点に近いノードから探索する
• キューを使って、次に探索するノードを管理する
• 同じノードを繰り返し処理しないように訪問済みの状態を管理する

今回使用するグラフ

今回は、次のようなノードの接続関係を使用する。

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["F"],
    "F": [],
}

この辞書は、各ノードから移動できる隣接ノードを表している。

例えば、次のように読み取れる。

• AからはBとCへ移動できる
• BからはDとEへ移動できる
• CからはFへ移動できる
• EからもFへ移動できる
• DとFには、その先の接続がない

イメージすると、次のような構造になる。

        A
       / \
      B   C
     / \   \
    D   E → F
         \→ F

実際にはFは一つのノードだが、CとEの両方から接続されている。

幅優先探索のソースコード

from collections import deque


def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        node = queue.popleft()

        if node not in visited:
            print(f"訪問: {node}")
            visited.add(node)

            queue.extend(
                neighbor
                for neighbor in graph[node]
                if neighbor not in visited
            )


graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["F"],
    "F": [],
}

bfs(graph, "A")

実行結果

訪問: A
訪問: B
訪問: C
訪問: D
訪問: E
訪問: F

Aに近いノードから、B、C、D、E、Fの順番で探索されている。

幅優先探索の基本的な流れ

処理の流れは、大きく次の4段階に分けられる。

1. スタートノードをキューに追加する
2. キューの先頭からノードを取り出す
3. 未訪問であれば訪問済みにし、隣接ノードをキューへ追加する
4. キューが空になるまで繰り返す

ここから、それぞれの処理を詳しく確認する。

Step1 : スタートノードをキューに追加する

queue = deque([start])

今回のスタートノードはA。

bfs関数の第二引数として渡した"A"が、startに格納される。

その値をdequeへ渡すことで、最初のキューが作成される。

deque(["A"])

dequeは、Pythonのcollectionsモジュールに含まれるデータ構造。

正式名称はdouble-ended queueで、先頭と末尾の両方から効率よくデータを追加・削除できる。

幅優先探索では、先に追加したデータから取り出すキューとして使用する。

Step1.5 : 訪問済みのノードを管理する

まずは4行目で、訪問済みのノードを格納する空の集合を定義している。

visitedは、すでに訪問したノードを保存する集合。

最初は、まだどのノードにも訪問していないため空になっている。

訪問したノードをここへ追加することで、同じノードを何度も処理することを防ぐ。

set()とは

重複のない要素の集まりを表すデータ型

Step2 : キューからノードを取り出す

8行目でpopleftメソッドでキューから取り出したノードをnodeに格納している。

popleft()は、キューの一番左側にある値を取り出すメソッド。

最初のキューにはAが格納されているため、nodeにはAが入る。

node = "A"
queue = deque([])

取り出したAがまだvisitedに存在しなければ、訪問済みとして追加する。

if node not in visited:
    print(f"訪問: {node}")
    visited.add(node)

9~11行目でvisitedにまだ格納されていないノードを格納している。

10行目の出力結果

最初に格納されている値

Step3 : 隣接ノードをキューへ追加する

次の処理では、現在のノードに隣接する未訪問のノードをキューへ追加する。

queue.extend(
    neighbor
    for neighbor in graph[node]
    if neighbor not in visited
)

Aの隣接ノードは、BとC。

graph["A"]

実行結果は次のようになる。

["B", "C"]

BとCはまだ訪問していないため、両方がキューへ追加される。

queue = deque(["B", "C"])

Step4 : 探索の流れを具体的に確認する

1回目：Aを取り出す

取り出したノード: A

訪問済み: A

追加するノード: B、C

キュー: B、C

2回目：Bを取り出す

Bの隣接ノードはDとE。

取り出したノード: B
訪問済み: A、B
追加するノード: D、E
キュー: C、D、E

3回目：Cを取り出す

Cの隣接ノードはF。

取り出したノード: C
訪問済み: A、B、C
追加するノード: F
キュー: D、E、F

4回目：Dを取り出す

Dには隣接ノードがない。

取り出したノード: D
訪問済み: A、B、C、D
追加するノード: なし
キュー: E、F

5回目：Eを取り出す

Eの隣接ノードはF。

この時点ではFはキューに入っているが、まだ訪問済みにはなっていない。

そのため、Fがもう一度キューへ追加される。

取り出したノード: E
訪問済み: A、B、C、D、E
追加するノード: F
キュー: F、F

6回目：最初のFを取り出す

取り出したノード: F
訪問済み: A、B、C、D、E、F
追加するノード: なし
キュー: F

7回目：2回目のFを取り出す

Fはすでにvisitedに存在している。

そのため、if node not in visitedの条件を満たさず、処理されない。

取り出したノード: F
すでに訪問済みのためスキップ
キュー: 空

キューが空になったため、whileループが終了する。

なぜFが二つキューに入るのか

最初は、Fが二つ存在しているように見えて混乱した。

しかし、実際にFというノードが二つあるわけではない。

Fには、CとEの両方から到達できる。

C → F
E → F

Cを処理したときにFがキューへ追加され、その後Eを処理したときにもFが追加される。

このコードでは、キューへ追加済みかどうかではなく、訪問済みかどうかを確認している。

Eを処理した時点では、Fはまだキューの中にあるだけで、訪問済みではない。そのため、もう一度追加される。

ただし、最初のFを処理した時点でvisitedへ登録されるため、2回目のFは処理されずに弾かれる。

重複してキューへ追加しない書き方

キューへの重複追加そのものを防ぐ場合は、ノードをキューへ追加する時点で訪問済みにする方法もある。

from collections import deque


def bfs(graph, start):
    visited = {start}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        print(f"訪問: {node}")

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

この書き方では、Fを最初にキューへ追加した時点でvisitedにも追加する。

そのため、Eを処理するときにはFがすでに登録されており、キューへ重複して追加されない。

こちらの方が、キューに同じノードが何度も入ることを防げる。

まとめ

幅優先探索は、キューを使ってスタート地点に近いノードから順番に探索するアルゴリズム。

今回のコードでは、次の役割を理解できた。

• dequeで次に探索するノードを管理する
• popleft()でキューの先頭からノードを取り出す
• visitedで訪問済みのノードを管理する
• graph[node]から隣接ノードを取得する
• キューが空になるまで探索を繰り返す

最初はコードを読んでも、何が起きているのか分からなかった。

しかし、キュー、現在のノード、訪問済みノードの中身を一つずつ追いかけることで、処理の流れが見えるようになった。

一つの仕組みを深く理解すると、似たようなコードも理解しやすくなる。

次は、今回理解した幅優先探索を使って、スタート地点からゴール地点までの最短経路を求める。