幅優先探索法: 近いところから広げよう
幅優先探索法は、スタート地点に近い場所から順番に調べていく方法です。
地図アプリで「今いる場所から一番近い駅、次に近い駅」と広げていくイメージです。
ルール
- スタート地点をキューに入れる
- キューの先頭から1つ取り出して調べる
- まだ行っていない隣の地点をキューに入れる
- 近い地点から順番に広がっていく
図で見る
コピペ用コード
from collections import deque
def breadth_first_search(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for next_node in graph[node]:
if next_node not in visited:
visited.add(next_node)
queue.append(next_node)
return order
graph = {
"A": ["B", "C"],
"B": ["D"],
"C": ["E"],
"D": [],
"E": [],
}
print(breadth_first_search(graph, "A"))
AOJで挑戦してみよう！
学んだレシピを実際に使って、ジャッジから「Accepted（正解）」を勝ち取ろう！