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

更新日時 2021/03/07

深さ優先探索とは「とにかく行けるとこまで行ってそれ以上進めなくなったら一歩戻ってそこから探索する」という探索方法。

幅優先探索とは「出発点に近い点から順に探索する」という探索方法。

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

深さ優先探索，幅優先探索でやりたいこと深さ優先探索や，幅優先探索は，グラフ探索に使えるアルゴリズムです。
グラフ探索とは，グラフ（ネットワーク）の頂点を全て探索したい！という問題です。
ただし，グラフは連結（どの頂点からどの頂点までもたどりつける）とします。

深さ優先探索

深さ優先探索（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などのもっと巨大なグラフになると線形時間でも遅いようです。