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となります。木を上から下、左から右に読み取った順番です。また、キューから削除される節点を順番に読み取っても同様の結果となります。
- 作者: R.セジウィック,Robert Sedgewick,野下浩平,佐藤創,星守,田口東
- 出版社/メーカー: 近代科学社
- 発売日: 1996/09/01
- メディア: 単行本
- 購入: 5人 クリック: 60回
- この商品を含むブログ (10件) を見る
追記(2010/11/23)
用語の誤りを訂正しました(幅優先検索 => 幅優先探索)