How Breadth First Search uses Queue

先日のエントリにて、幅優先探索を用いたダイクストラアルゴリズムを考察しました。今回は、幅優先探索が如何にキューを用いるかをまとめてみました。

名著アルゴリズムCでは、幅優先探索はレベル順(level-order)の走査として、第1巻第4章、木の章にてごく簡単に記載されています。以下は、アルゴリズムCに記載されているコードを抜粋したものです。書籍を読むたびに、その簡潔さに改めて驚かされます。

traverse(struct node *t)
{
  put(t);
  while (! queueempty()) {
    t = get(); visit(t);
    if (t->l != z) put(t->l);
    if (t->r != z) put(t->r);
  }
}

さて、幅優先探索はキューに積み上げた節点を1回の反復につき1つ処理します。処理する節点が子の節点群を持つ場合はそれらをキューに積みます。新たにキューに積まれた子の節点群は反復によって探索が進むにつれ処理され、キューから削除されます。

今回は幅優先探索に用いられるキューの動作を、同じくアルゴリズムC第1巻第3章、基本データ構造にて示されているキューの動作例と並べてみました。

反復が始まる前に、まず根の節点であるPがキューに追加されます。この状態が、図の一番上の状態です。初めの反復では、キューに保持されているPを取得し、処理を行います。同時に、節点Pをキューから削除します。キューから節点が削除される様子は、小さな四角形を描画することで表しています。節点Pは子の節点MとLを持っているため、これをキューに積みます。次の反復では、先ほど積まれた初めの節点Mを処理し、その子である節点Sをキューに積みます。以後、同様に反復を行います。全ての節点を訪れた後にキューは空となり、幅優先探索は終了となります。

結果として、幅優先探索を用いてこの木の節点を訪れる順番はPMLSEAARTEEとなります。木を上から下、左から右に読み取った順番です。また、キューから削除される節点を順番に読み取っても同様の結果となります。

アルゴリズムC〈第1巻〉基礎・整列

アルゴリズムC〈第1巻〉基礎・整列

追記(2010/11/23)

用語の誤りを訂正しました(幅優先検索 => 幅優先探索)