幅優先探索とは

はばゆうせんたんさく

グラフや木を、出発点から近い順(辺1本で行ける頂点、次に2本で行ける頂点…)に訪れる探索の方法。キューを使って実装し、辺に重みのないグラフでは、出発点から各頂点への最短の辺の数が求まる。英語の頭文字からBFSともいう。

「幅優先探索」は、1分野の4問の練習問題に出てきます(データ構造とアルゴリズムなど)。

この用語の分野: データ構造とアルゴリズム

幅優先探索の練習問題に挑戦

空のキューに A、B、C の順に要素を入れ、1つ取り出し、D を入れて1つ取り出し、E を入れて1つ取り出した。取り出された要素を順に並べたものはどれか。

AA, B, C
BC, D, E
CC, B, A

答えと解説を見る

正解：A. A, B, C

キューは先に入れたものから順に取り出す先入れ先出し(FIFO)の構造です。A、B、C を入れた後の最初の取り出しでは A が出ます。その後 D や E を後ろに加えても、先頭にある B、C が先に出るので、取り出される順は A、B、C で、最後に D と E が残ります。C、D、E は、そのつど最後に入れたものを出すスタック(LIFO)として扱った場合の順です。キューは、プリンタの印刷待ちや、タスク間でデータを受け渡すメッセージキュー、幅優先探索などに使われます。

頂点が100万個、辺が300万本ほどの道路網のように、頂点の数に比べて辺の少ない(疎な)グラフをメモリに記憶する方法として適切なものはどれか。

A隣接行列。2つの頂点の間に辺があるかを O(1) で調べられ、記憶領域も最も少なく済む
B隣接リスト。記憶領域は頂点の数と辺の数の和に比例し、ある頂点から出る辺を順にたどるのに向いている
C隣接行列。記憶領域は辺の数だけに比例する

答えと解説を見る

正解：B. 隣接リスト。記憶領域は頂点の数と辺の数の和に比例し、ある頂点から出る辺を順にたどるのに向いている

隣接行列は頂点数 V に対して V×V の表を使うので、100万頂点では10¹²個の要素が必要で、1要素1ビットでも約125 GBになります。隣接リストは各頂点につながる頂点だけを並べるので、記憶領域は O(V + E) で、この例なら数百万件程度で済みます。隣接行列は辺の有無を O(1) で調べられる利点があり、辺の多い(密な)グラフや頂点の少ないグラフに向いています。幅優先探索やダイクストラ法のように、頂点から出る辺を順にたどる処理では、隣接リストの方が効率よく動きます。