幅優先探索――グラフ探索
では、ここからアルゴリズムを紹介していきましょう。最初に紹介するのはグラフを探索するアルゴリズムの「幅優先探索」です。
そもそもコンピューターサイエンスでいうグラフとは、複数個の頂点(ノード)が辺で結ばれたものをいいます。人間関係(ソーシャルグラフ)、路線図、コンピューターネットワークなど、様々なものをグラフで表現できます。
これらのグラフを探索するためのアルゴリズムの一つである幅優先探索は、全貌のわからないグラフにおいて、始点から辺を辿りながら頂点を探索し、指定された頂点(ゴール)に辿り着けば目的達成です。端的には、頂点を探索する際、始点に近い頂点から優先的に探索していくアルゴリズムです。
![リスト2-1 リスト2-1](https://codezine.jp/static/images/article/10198/10198_02_1.jpg)
まず、始点を定めましょう。今回はAです。ゴールとしてGを設定しますが、Gがどこにあるかは最初の時点ではわかりません。
![リスト2-2 リスト2-2](https://codezine.jp/static/images/article/10198/10198_02_2.jpg)
Aから辿れる頂点B、C、Dが次に進む頂点の候補です。
![リスト2-3 リスト2-3](https://codezine.jp/static/images/article/10198/10198_02_3.jpg)
候補の中から頂点を一つ選びます。選択の基準は、最も早く候補に追加されたものです(同じタイミングのときはどれでも構いません)。
![リスト2-4 リスト2-4](https://codezine.jp/static/images/article/10198/10198_02_4.jpg)
今回はB、C、Dが同じタイミングで候補となったのでBを選択します。
![リスト2-5 リスト2-5](https://codezine.jp/static/images/article/10198/10198_02_5.jpg)
Bに移動すると、Aが探索済みとなります。
![リスト2-6 リスト2-6](https://codezine.jp/static/images/article/10198/10198_02_5.jpg)
Bから辿れるEとFを候補に追加しましょう。これで候補がC、D、E、Fとなりました。
![リスト2-7 リスト2-7](https://codezine.jp/static/images/article/10198/10198_02_7.jpg)
C、D、E、Fのうち、最も早く候補になったのはCとDです。今回も左側のCを選択します。
![リスト2-8 リスト2-8](https://codezine.jp/static/images/article/10198/10198_02_8.jpg)
Bから、選択したCに移動します。Bが探索済みとなります。
![リスト2-9 リスト2-9](https://codezine.jp/static/images/article/10198/10198_02_9.jpg)
Cから辿れるHが新たに候補に加わります。現在の候補はD、E、F、Hです。
![リスト2-10 リスト2-10](https://codezine.jp/static/images/article/10198/10198_02_10.jpg)
このように、ゴールに辿り着くか、すべての頂点を探索し終えるまで探索を繰り返します。
![リスト2-11 リスト2-11](https://codezine.jp/static/images/article/10198/10198_02_11.jpg)
![リスト2-12 リスト2-12](https://codezine.jp/static/images/article/10198/10198_02_12.jpg)
![リスト2-13 リスト2-13](https://codezine.jp/static/images/article/10198/10198_02_13.jpg)
今回の例での選択順はA、B、C、D、E、F、H、I、J、K、そしてGとなりました。
幅優先探索では文字どおり幅広く探索を行っていく特徴があります。当たり前のことですが、始点の近くにゴールがあるほうが探索が早く終了します。
ちなみに、ここまで例として用いてきた連結して閉路のないグラフは木と呼ばれています。また、始点と終点が同じ頂点である(閉路がある)グラフも同様に探索することができます。