BFS（幅優先探索） とは？

スタート地点から1歩で行ける場所を全部訪問して、次に2歩で行ける場所を全部訪問して……という風に、近い順に広がっていく探索法だよ。

まさにその通り！波紋が同心円状に広がるように探索するんだ。だから最初にゴールに到達したルートが最短経路だと保証されるよ。

キューというデータ構造を使うんだ。先に入れたものから順に取り出す仕組みで、行列の先頭から処理するイメージだね。

DFSは一本道をどこまでも深く進んでから戻るタイプ。BFSは浅いところを全部見てから深くに進む。迷路の最短ルートを見つけたいならBFS、全ルートをとにかく列挙したいならDFSが向いているよ。

カーナビの最短ルート検索、SNSの「知り合いかも」機能、ネットワークのブロードキャスト、パズルの最小手数解法など、かなり幅広いよ。計算量はO(V+E)で、ノード数Vとエッジ数Eに比例するから大規模グラフではメモリ消費に注意が必要だね。