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

アルゴリズム
スポンサーリンク
学ぶ者
学ぶ者

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

筆者
筆者

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

スポンサーリンク

幅優先探索とは

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

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

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

グラフの基本的操作

グラフの例

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

辺も同様です。

参照に関する図

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

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

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

スポンサーリンク

幅優先探索の参照の流れ

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

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

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

ステップ1

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

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

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

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

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

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

ステップ2

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

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

終了となります。

幅優先木

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

幅優先木

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

まとめ

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

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

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