IT用語集 › プログラミング › BFS（幅優先探索）
ある深さのノードをすべて訪れてから次の深さへ進むグラフ探索。FIFOキューで実装する。
重みのないグラフでは最短経路を保証する。典型的な用途は、ノード間の最小ホップ数（LinkedInの「3次のつながり」）、Webクロール、木のレベル順走査、「最少手数で勝つ」ゲームAIなど。計算量は時間O(V+E)、最悪の空間O(V)。比較対象はDFS（キューの代わりにスタックを使い、深さ優先で進む）と、辺に重みがある場合のDijkstraだ。