Pythonアルゴリズム

Pythonの幅優先探索(BFS)

このレッスンでは、幅優先探索とdequeのキューを使って、グラフを階層ごとにたどります。

  • 中級
  • 約2分で読めます
  • 実行できるサンプル 1 件

はじめに

どんな問題を解決するか

ソーシャルネットワークで、ある人から別の人まで何ステップでたどり着けるか。迷路のあるマスから出口まで何歩か。幅優先探索は距離の輪を広げるように探索するので、最初にあるノードに到達したときの道が最短経路です。

身近なたとえ

幅優先探索は池の波紋のようなものです。スタート地点に石を落とすと、波紋はまず1歩離れたすべてに届き、次に2歩離れたすべてに届きます。近いものすべてに届く前に、遠いものに触れることはありません。

池の波紋からコードへ
queue = deque(["A"])🪨 A に石を落とす
node = queue.popleft()🌊 距離の順に次のノードを取る
if neighbor not in visited:🔎 まだ届いていない?
queue.append(neighbor)➕ 次の輪に加える
キューを使い、近いノードから先に。
ひと言でいうと

幅優先探索(BFS)はスタートのノードから層ごとにグラフを訪れ、キューを使います。そのため重みのないグラフで最短経路を見つけます。

重要なポイント

  1. queue は、探索を待っているノードを古い順に持ちます。
  2. visited は見つけたノードを記録するので、同じノードを2回追加せず、閉路で無限ループにもなりません。
  3. node = queue.popleft() で次のノードを取り、まだ訪れていない隣のノードがキューの最後に並びます。
  4. order は A、その隣の B と C、さらに1層先の D と E を示します。

どんな場面で使う?

  • 重みのないグラフ、格子、迷路での最短経路。
  • ソーシャルネットワークでの隔たりの次数。
  • Web クローラーや、スタート地点から到達できるものすべての発見。

使わなくてよいとき

  • 道路の距離のように辺のコストが違う場合:ダイクストラ法を使います。
  • バックトラッキングのように1つの道を最後まで探る必要がある場合:深さ優先探索を使います。

Pythonの幅優先探索(BFS)のビジュアライザー

O(V + E)

再生またはステップを使って、比較とデータ移動を順に確認できます。

サンプルコード

コードを実行 →
main.py
from collections import deque

graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
queue = deque(["A"])
visited = {"A"}
order = []

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

print(order)
この例の実行ボタンを作成

実行結果

['A', 'B', 'C', 'D', 'E']

コードの解説

キューqueueには訪問を待つ頂点が入り、追加した順番どおりに取り出されます。セットvisitedはすでに見つけた頂点を記録し、グラフに閉路があっても同じ頂点を何度も訪れないようにします。訪問順はA、B、C、D、Eで、計算量はO(V + E)です(Vは頂点の数、Eは辺の数)。

値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。

発展問題

下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。

  1. 空のリスト、要素が1つだけのリスト、重複した値を含むリストで試す。
  2. 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
  3. 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
Pythonコンパイラで実行 →

よくある間違い

訪問済みの印を付けるのが遅すぎる

キューから取り出すときにだけ印を付けると、同じノードが何度も追加されることがあります。

問題
node = queue.popleft()
visited.add(node)
for neighbor in graph[node]:
    if neighbor not in visited:
        queue.append(neighbor)
修正
for neighbor in graph[node]:
    if neighbor not in visited:
        visited.add(neighbor)
        queue.append(neighbor)

このレッスンを終えましたか?

学習済みにすると進み具合を記録できます。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

すべてのチャレンジ