2025.07.26(更新日: 2025.07.26)
幅優先探索をマスターする
はじめに
上長からの幅優先探索の第一引数に渡すデータ作成のリクエストに瞬時に対応することができなかった。
エンジニアとしての実力が可視化された瞬間だった。
スキルアップできる、実力不足を痛感できる環境にいることに感謝して、圧倒的な実力を示していきたい。
手始めに、Pythonで幅優先探索を行おう。
幅優先探索(Breadth-First Search, 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(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。

bfs関数の第二引数に渡ってくる。そして、dequeに渡す。

deque(double-ended queue)は、両端からデータの追加削除ができるcollectionsモジュールに含まれるデータ構造。

キューからノードを取り出し、訪問済みにする
まずは4行目で、訪問済みのノードを格納する空の集合を定義している。


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

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

10行目の出力結果

最初に格納されている値

そのノードに隣接するノードをキューに追加(まだ訪問していない場合)

queue.extend([neighbor for neighbor in graph[node] if neighbor not in visited])
よくわからなかったので、GPTに相談してみた。


キューが空になるまで繰り返す

訪問: A
訪問: B
訪問: C
訪問: D
訪問: E
訪問: F
ここまで書いてみたが、よくわからない
具体的にみていこう。
グラフとは

これは何を意味するのか?
GPTに聞いてみた。



幅優先探索なので
探索をする。
先ほどの図を探索していくということだろう。

Aスタート

A訪問済み

キューに未訪問の隣接ノードを追加
queue.extend([neighbor for neighbor in graph[node] if neighbor not in visited])
リストオブジェクト生成

neighbor


return

queueに値が入る

while繰り返し

popleft

理解した
ここまでくるとだいぶわかってきた。
ひとつ完全理解すると、他の似たようなことも理解できるようになる。
Fが二つ
Fは二つある。


最初はnodeに追加される。

2回目はvisitedにあるので、弾かれる。


コメントを残す