最短経路を求めるのに便利な「幅優先探索」

第13回では、「進めるだけ進み、行き詰まったら1歩戻る」という方針でグラフを探索する「深さ優先探索」を取り上げましたが、グラフに関するアルゴリズムはこれだけではありません。今回は最短経路を求めるときにも使える「幅優先探索」を紹介します。

第13回「身近な『掃除』を例に考える、『深さ優先探索』とは?」はこちらから

幅優先探索とは

幅優先探索は、スタートに近い頂点から順番にグラフを探索していくアルゴリズムです。英語で「 Breadth First Search 」と書くため、略して BFS と呼ばれることもあります。

幅優先探索のイメージを理解するために、冷房の問題を考えてみましょう。具体的には、部屋 1 の冷房のスイッチを入れ、部屋 1 が涼しくなったという状況を考えます。1 分で「隣接する部屋」が涼しくなるとき、各部屋は何分後に涼しくなるのでしょうか。

答えは部屋 1 から順に 0 分・1 分・1 分・2 分・3 分・3 分です。冷房の場所（部屋 1）から考えていくと、下図のようにして答えを求めることができます。冷房の効き具合を 1 分ごとにシミュレーションしていると捉えることもできますね。