概要
概要
幅優先探索は、始点からの距離が近い順に探索を進めます。キューを使うのが本質です。
グラフ / BFS（幅優先探索）
幅優先探索は、始点からの距離が近い順に探索を進めます。キューを使うのが本質です。
目次
このページでわかること
概要
幅優先探索は、始点からの距離が近い順に探索を進めます。キューを使うのが本質です。
考え方
enqueue start
while queue not empty
pop front
enqueue unvisited neighbors要点
O(V + E)
O(V)
Queue
最短距離(重みなし)
補足
1 手先、2 手先という順番で広がります。
frontier を青、訪問済みを灰で出すとわかりやすいです。
重みなしグラフの最短経路と相性がよいです。
動きで確認
ここでは「どの頂点が注目か」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。