実装パターン

キューによる実装

二重バッファによる実装

求まるもの

• 始点からの距離
• 始点からたどり着けるか

派生パターン

• 複数始点 BFS
  • 超頂点を使う
  • 最初に複数頂点を Queue に入れる
• 0,1-BFS
  • VecDeque を使う
  • 二重バッファを使う
• 0,1,2-BFS
  • 三重バッファを使う
• その他
  • ABC413 F - No Passage

メモ

• 探索空間 (グラフのサイズ) 自体はとても大きいが、解がスタートから十分近いところにあることがわかっている場合は、DFS より BFS の方が良いことがある。
  • 参考: BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜 #AtCoder - Qiita