1 基本概念
レベル順走査は、木やグラフを、始点に近い層から順にたどる探索法である。各要素を深さごとにまとめて扱うため、構造全体を段階的に把握しやすい。一般には幅優先探索の代表例として説明され、情報検索、木の解析、到達経路の検討などで広く利用される。
1.1 定義
この走査では、開始点からの距離が短い要素を先に訪れ、同じ層にある要素を横方向へ処理する。深い位置へ進む前に、現在の階層をおおむね完了させる点が特徴である。結果として、訪問順は「近いものから遠いものへ」という性質を示す。
1.2 対象となる構造
レベル順走査は、階層をもつデータに特に適している。親子関係が明確な木だけでなく、頂点と辺からなる一般的なグラフにも適用できる。ただし、グラフでは循環がある場合を考慮する必要がある。
1.2.1 木構造
木構造では、根を起点として、子要素を上から下へ順に処理する。各層のノードをまとめて見ることで、全体の形を把握しやすい。二分木のような規則的な構造では、左右の順序も含めて整理しやすい。
1.2.2 グラフ構造
グラフでは、始点から到達可能な頂点を距離の小さい順に調べる。辺の張り方によって進み方は変わるが、同一の距離帯をまとめて扱うという基本は共通する。連結性の確認や経路探索の基礎としても扱われる。
1.3 他の走査法との違い
深さ優先的な走査が一つの枝を先へ深く追うのに対し、レベル順走査は横方向の広がりを優先する。前者が局所的な探索に向きやすいのに対して、後者は距離や段階を重視する場面で役立つ。処理順の違いにより、得られる情報の並びも変化する。
2 仕組み
レベル順走査は、現在処理中の層の要素を順に取り出し、その次の層を後から追加することで進む。これにより、訪問の順序が自然に制御される。木でもグラフでも、基本的な考え方は同じである。
2.1 探索の順序
最初に始点を処理し、その近傍を次に扱う。取り出した要素から未処理の隣接要素をまとめて記録し、先に入れたものから順に訪れる。こうした流れにより、同じ深さの候補が連続して現れる。
2.2 使用する補助記憶
この方法では、後で処理する要素を一時的に保存する仕組みが必要になる。代表的なのは待ち行列であり、追加した順に取り出せることが重要である。グラフの場合は、重複を避けるための管理情報も欠かせない。
2.2.1 待ち行列の役割
待ち行列は、次に調べる候補を順序どおり保持する。先に見つかった要素が先に取り出されるため、層の順番が崩れにくい。これによって、探索の進行が安定し、実装も明快になる。
2.2.2 訪問済み管理
グラフでは、同じ頂点を何度も処理しないように、訪問済みかどうかを記録する。これにより、循環や多重経路による無限反復を避けられる。木では通常不要だが、一般のネットワークでは不可欠である。
2.3 代表的な処理手順
まず始点を待ち行列に入れ、訪問済みとして記録する。次に、待ち行列から一つずつ取り出して処理し、未訪問の隣接要素を追加する。この流れを候補がなくなるまで繰り返すことで、全体を層ごとに走査できる。
3 実装
実装では、対象の構造に応じて管理方法を選ぶ。木の場合は親子関係が単純であるため、比較的そのまま処理しやすい。グラフでは、接続関係の表現と重複制御がより重要になる。
3.1 木に対する実装
木の走査は、根から始めて子を順に展開する形で実現される。子の並び順を保つことで、結果の順序も安定する。各層の要素をまとめて扱うと、構造の把握にも適する。
3.1.1 一般木
一般木では、各ノードが任意個の子を持つ。ノードを取り出したら、その子を左から右、あるいは登録順に待ち行列へ追加する。これだけで、層ごとの訪問が自然に実現される。
3.1.2 二分木
二分木では、各ノードの左部分木と右部分木を順に処理する。左右の順番を固定すれば、結果の並びも再現しやすい。構造が単純なため、教育用の例としてもよく用いられる。
3.2 グラフに対する実装
グラフでは、隣接関係を適切に保持しながら、訪問の重複を防ぐ必要がある。隣接表を使うと、各頂点から行ける先を効率よく列挙できる。探索範囲が広い場合でも、扱いが比較的明確である。
3.2.1 隣接表を用いる方法
隣接表では、各頂点に接続先の一覧を持たせる。頂点を処理するたびに、その一覧を参照して未訪問の隣接頂点を待ち行列へ入れる。疎なグラフでは特に扱いやすい。
3.2.2 重複訪問の防止
重複訪問を避けるには、待ち行列に入れる段階で訪問済みにする方法が一般的である。これにより、同じ頂点が複数回追加されるのを抑えられる。結果として、処理量の増加も防ぎやすい。
3.3 計算量
木では、各ノードを一度ずつ処理するため、基本的な計算量は要素数に比例する。グラフでも、頂点と辺を適切に追跡すれば、全体として線形時間で扱えることが多い。必要な追加記憶は、主に待ち行列と訪問管理に由来する。
4 応用
レベル順走査は、構造の層を順番に見る必要がある場面で有用である。単に順序を決めるだけでなく、段階的な比較や集計にも向いている。検索や解析、経路問題の初期段階などで採用されることがある。
4.1 情報検索分野での利用
情報検索では、候補を近いものから順に広げる考え方に応用できる。まず粗い一致を確認し、その後に詳細な条件を検討する流れが取りやすい。候補群を層状に扱う発想は、段階的な絞り込みと相性がよい。
4.1.1 階層的な候補探索
候補をカテゴリーや距離の近さで分け、上位の層から順に調べる方法がある。これにより、重要度の高い対象を先に発見しやすい。大規模な集合でも、探索の方向を整理しやすくなる。
4.1.2 関連度の段階的確認
最初に広い条件で対象を拾い、次に関連度の高いものへ絞り込む使い方がある。層を追って確認するため、確認作業の順番が明快になる。検索結果の優先順位付けにも役立つ。
4.2 データ構造の解析
構造を層ごとに見ることで、偏りや分布を把握しやすくなる。ノード数の増え方、深さごとの密度、分岐の形などを整理する際に便利である。解析の入口としても使われる。
4.2.1 深さごとの集計
各層に属する要素数を数えることで、深さ別の統計を取れる。これにより、構造の広がり方や集中度を把握しやすい。木のバランス確認にも応用される。
4.2.2 層ごとの可視化
レベル順で並べると、画面表示や図示の際に見通しがよくなる。上から下へ順に配置する方法は、階層関係を直感的に示しやすい。教育や説明資料でも利用価値が高い。
4.3 問題解決への応用
レベル順走査は、距離や手数を最小にしたい場面で特に効果を発揮する。到達可能性を段階的に確認できるため、探索問題の初期解法として有力である。条件付き列挙にも向く。
4.3.1 最短手数の探索
各層が手数や辺数の増加に対応するため、最初に見つかった解が最短であることを利用できる。迷路、状態遷移、簡単な経路問題などで有効である。最小ステップを求める際の基本手法の一つとされる。
4.3.2 階層的な列挙
条件を満たす対象を、浅い層から順に列挙する用途がある。全候補を無差別に並べるより、段階を区切って出力できる点が利点である。優先順位を保ちながら候補を広げる問題に適している。