幅優先探索（BFS） とは？

出発点から辺を1本で届く点、2本で届く点という順に調べるよ。波のように広がるイメージだけれど、画面上の距離ではなく、通る辺の数で近さを考える。出発点からつながっていない点には届かないんだ。

出発点を探索済みにしてキューへ入れる。先頭から点を取り出し、その隣の点で未探索のものを探索済みにして末尾へ追加する。キューが空になるまで繰り返すよ。追加時の記録があれば、同じ点を何度も入れたり、循環で終わらなくなったりするのを防げるんだ。

1回の移動の費用が同じ迷路で、最少の移動回数を調べる例があるよ。SNSで何本の友達リンクをたどれば届くかを調べることもできる。道路ごとの所要時間のように重みが違う場合は、BFSの辺の数が最少でも時間が最短とは限らないね。

DFSは1本の道を深くたどり、BFSは同じ距離の点を先に調べるよ。どちらも到達できる点を調べられるけれど、重みなしの最短経路を求めるならBFSが使える。同じ距離の点が多いとキューが大きくなる。探索済みの管理はDFSでも必要になるね。

隣接リストでグラフを表し、キューの追加・取り出しを一定時間で行う実装なら、ノード数Vと辺の数Eに対してO(V+E)だよ。無向グラフでは1本の辺を両端から確認することがあるけれど、この計算量は変わらない。探索済みやキューなどに使う追加の空間はO(V)だね。