幅優先探索とは

幅優先探索とは、木やグラフをたどるとき、出発点に近いところから順に、同じ深さの地点をすべて調べてから次の深さへ進む探索アルゴリズムです。英語の頭文字をとってBFSとも呼ばれます。AIの経路探索に使われるA*探索などの土台にあたる、基本の探索方法の一つなのです。

最短ルートを見つけられる強み

幅優先探索の大きな特徴は、すべての分かれ道に同じ重みがある場合、出発点からゴールまでの最短ルートを必ず見つけられる点です。波紋が水面に同心円状に広がるように、近い地点から一段ずつ調べていくため、最初に到達できた道が、そのまま最短になるのがミソ。SNSで「友だちの友だち」を近い順にたどり、ある人まで何人でつながるかを数えるような場面も、根っこは同じ考え方です。ただし一段ごとに調べる範囲が大きく広がるため、深い場所を一気に掘り下げたいなら深さ優先探索のほうが向くでしょう。

幅優先探索に関するよくある質問

幅優先探索と深さ優先探索は何が違いますか？

探す順番が逆です。幅優先探索は出発点に近いところから横へ広げて調べ、深さ優先探索は一つの道をできるだけ奥まで進んでから引き返します。最短ルートを確実に知りたいときは幅優先探索が向いています。

幅優先探索は私たちの身近でどう使われていますか？

ものごとを近い順に一段ずつ調べたい場面で活躍します。たとえば最小の乗り換え回数で目的の駅に着く経路や、通信網でいちばん近いサーバーを探す処理などです。