幅優先探索(BFS)とは？わかりやすく図を用いて解説！

学ぶ者

幅優先探索について詳しく知りたいです！

筆者

一つ一つ手順を見ていけば理解できるようになるので一緒に学んでいきましょう！

幅優先探索とは

幅優先探索(Breadth First Search)とは、木構造やグラフの探索を行う代表的な探索の一つです。

グラフ中の点や辺を複数参照することで目的の要素を見つける操作をします。

グラフを探索するときの基本的な操作を説明していきます。

丸い点とそれを繋ぐ辺で構成されたものをグラフといい、それぞれの点には違いがわかるように、添字で番号が付けられることが多いです。(もしくは違うローマ字を使うなど。)

辺も同様です。

参照する時には点には数字を記入していきます。

そして、通った辺にも何番目に通ったのかを()内に記載します。

こうすることで、参照したことのある点に２度行くことを防げます。

1.まず参照する時には、辺で繋がっていて参照したことのない点に行きます。

今回の図では、a2をスタート地点として周りの点を参照していきましょう。

参照する順はどんなものでも良いですが、よく行われる点の添字が低いものからにしてみます。

これで1番目の点から参照できるものは全て参照し終えました。

2.参照が終わっている点から、まだ参照していないもので、参照できる点を探す。

a2から参照した点はa1,a3,a4の３つあります。

添字が小さいものから順に探索を優先します。

しかしa1を見ると、繋がっている点が全て参照されています。

a3も同じです。そのため、a4を次の参照する起点とします。

a2の時と同じように参照するとa5とa6を参照できました。

a5とa6から参照できる点がないということは、全ての点が参照できたということなので

終了となります。

おまけとして、先ほど探索したものを木構造にした幅優先木を紹介しておきます。

先ほどのグラフよりも見やすくなったと思います。

探索の代表的なものの一つである幅優先探索を紹介しました！

落ち着いてみれば簡単な内容になっていますので、わからなかった場合はステップごとに切り分けて考えてみましょう。

よく迷路の探索アルゴリズムにも使われたりするので、覚えておくのも良いでしょう。