幅優先探索(BFS)

重みなしグラフの最短経路、階層ごとの処理、Web クロール、SNS 上の距離(「六次の隔たり」)などの標準的なアルゴリズムである。計算量は O(V+E)。幅の広いグラフでは「フロンティア」全体をメモリに保持するため、メモリが問題になりうる。変種の双方向 BFS は両端から同時に探索し、平方根オーダーの高速化が得られる。Dijkstra 法は BFS を重み付きグラフに一般化したものである。