読者です 読者をやめる 読者になる 読者になる

情報系 備忘録

情報系学習者の備忘録 間違ってるかも。

幅優先探索

今回は、アルゴリズムの一つである幅優先探索について。

幅優先探索は、木構造やグラフのデータを探索するアルゴリズムの一種であり、対照的なアルゴリズムとして深さ優先探索があります。こちらについても後々書くつもりです。



木構造の一つのNodeは簡単に以下のように定義できます。

class TreeNode{

int data;
TreeNode right;
TreeNode left ;

}

幅優先探索はその名の通り、幅を優先する探索方法であり、あるノードに対してそのノードに近接したノードから順に調べていくものです。

Queueというデータ構造を用いて実装することができます。
ちなみにQueueとは、FIFO(First In First Out)という特徴を備えたものであり、両方があいた筒状のものをイメージしていただければよいかなと思います。


アルゴリズムとしては以下のようになります。

  1. ノードを受け取り、Queueに追加する
  2. Queueがら空の場合は失敗。
  3. Queueからノードを取り出し、そのノードが目標であればそのデータを返し、停止する。
  4. 調べたノードの子ノードを全てQueueに追加する。この時にその子ノードからノードに対してポインタを張る。
  5. 2に戻る。

コードとしては以下のようになります。

void BredthFirstSearch(Node firstnode){
  
  Queueを生成する。
  目標なら終了。
  firstnodeに探索済みの印をつける。
  Queueにfirstnodeを追加する。
  
  while(Queueが空でない){
    Queueからノードを取り出す。
    foreach(取り出したノードの子ノード){
      探索済みの印をつける。
      目標なら終了。
      Queueに追加する。
    }
  }
}

幅優先探索の特徴は完全性、また空間計算量が探索対象が大きい場合に非常に大きくなることです。
一般的に最適性があります。

全てのノードを調べたい、またはあるノードを見つけたいといった場合に深さ優先探索ではなく幅優先探索が用いられることが多いようです。