はじめに
どんな問題を解決するか
ソーシャルネットワークで、ある人から別の人まで何ステップでたどり着けるか。迷路のあるマスから出口まで何歩か。幅優先探索は距離の輪を広げるように探索するので、最初にあるノードに到達したときの道が最短経路です。
身近なたとえ
幅優先探索は池の波紋のようなものです。スタート地点に石を落とすと、波紋はまず1歩離れたすべてに届き、次に2歩離れたすべてに届きます。近いものすべてに届く前に、遠いものに触れることはありません。
池の波紋からコードへ
queue = deque(["A"])🪨 A に石を落とすnode = queue.popleft()🌊 距離の順に次のノードを取るif neighbor not in visited:🔎 まだ届いていない?queue.append(neighbor)➕ 次の輪に加えるひと言でいうと
幅優先探索(BFS)はスタートのノードから層ごとにグラフを訪れ、キューを使います。そのため重みのないグラフで最短経路を見つけます。
重要なポイント
queueは、探索を待っているノードを古い順に持ちます。visitedは見つけたノードを記録するので、同じノードを2回追加せず、閉路で無限ループにもなりません。node = queue.popleft()で次のノードを取り、まだ訪れていない隣のノードがキューの最後に並びます。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つだけのリスト、重複した値を含むリストで試す。
- 各ステップの後の状態を表示して、アルゴリズムの動きを観察する。
- 要素が100個、1,000個、10,000個のときの実行時間を測り、別の解き方と比べる。
よくある間違い
訪問済みの印を付けるのが遅すぎる
キューから取り出すときにだけ印を付けると、同じノードが何度も追加されることがあります。
問題
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 のレビューも受けられます。
- Can We Split Into Two Teams? Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. 中級
- Tree Diameter A tree is a connected undirected graph with no cycles. 中級
- Count Islands Count groups of connected land cells in a grid. 中級