2015/09/21

深さ優先探索と幅優先探索

分野: グラフ理論  レベル: 大学数学

この記事ではグラフ探索の二つの考え方「深さ優先探索」「幅優先探索」について解説します。非常に基本的なグラフアルゴリズムです。

やりたいこと

今回はグラフ(ネットワーク)の全頂点を探索するアルゴリズムについて考えます。

ただし,グラフは連結(どの頂点からどの頂点までもたどりつける)とします。

深さ優先探索

深さ優先探索(depth-first search, DFS)は大雑把に言うと,とにかく行けるとこまで行ってそれ以上進めなくなったら一歩戻ってまた探索するという方法です。

深さ優先探索の例

深さ優先探索の例:頂点 $A$ から出発してアルファベット順に探索する。

解説

ぶつかるまで未訪問の頂点を適当に進む $A→B→C$
必要なだけ戻る $C→B$
ぶつかるまで未訪問の頂点を適当に進む $B→D$
必要なだけ戻る $D→B→A$
ぶつかるまで未訪問の頂点を適当に進む $A→E→F$
以下同様

「一番最近(最後に)見たものの周りを最初に探索する」というlast in, first outの精神です。実装にはスタックというデータ構造を使います。カップスタックというカップを積み重ねる競技を知っているとイメージしやすいでしょう。

なお,深さ優先探索は迷路の解法にも使えます(壁に沿って進む感じ)。

幅優先探索

幅優先探索(breath-first search, BFS)は大雑把に言うと,出発点に近い点から順に探索するという方法です。

幅優先探索の例

幅優先探索の例:頂点 $A$ から出発してアルファベット順に探索する。

解説

$A$ に隣接しているものを探索する($B,C,D$)
$B$ に隣接しており未訪問のものを探索する($E,F$)
$C$ に隣接しており未訪問のものを探索する($G,H$)
以下同様

「一番最初に見たものの周りを最初に探索する」というfirst in, first outの精神です。実装にはキューというデータ構造を使います。

計算時間

深さ優先探索または幅優先探索を使うことで,頂点数 $|V|$,辺の数 $|E|$ のグラフの頂点は線形時間(高々 $|V|+|E|$ に比例する時間)で探索できます。

辺の数が一億本とかの巨大なグラフでもコンピューターを使えば探索することができます!

Facebookなどのもっと巨大なグラフになると線形時間でも遅いようです。
分野: グラフ理論  レベル: 大学数学