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

深さ優先探索，幅優先探索でやりたいこと

深さ優先探索や，幅優先探索は，グラフ探索に使えるアルゴリズムです。

グラフ探索とは，グラフ（ネットワーク）の頂点を全て探索したい，という問題です。

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

深さ優先探索

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

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

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

幅優先探索

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

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

計算時間

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

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