深さ優先探索(DFS)と幅優先探索(BFS)を図解でわかりやすく解説
この記事でわかること
- 深さ優先探索(DFS)と幅優先探索(BFS)を図解でわかりやすく解説 がどんな問題を解くための考え方か
- 基本アイデアと処理の流れ
- 実装するときに注意する点
- 計算量の見方
全体像
はじめに
深さ優先探索(DFS)と幅優先探索(BFS)は、グラフや木を探索するときの基本になるアルゴリズムです。
どちらも「未訪問の頂点をたどる」という点は同じですが、次に見る頂点の選び方が違います。
- DFS: 進めるところまで深く進む
- BFS: 近いところから順番に広げる
この記事では、同じグラフを使ってDFSとBFSの違いを整理し、最後にC#で実装してみます。
今回使うグラフ
以下のような無向グラフを例にします。
隣接リストでは、次のように表せます。
0: 1, 2
1: 0, 3, 4
2: 0, 5
3: 1
4: 1
5: 2
開始地点は 0 とします。
DFSとは？
DFS(Depth First Search)は、日本語では深さ優先探索と呼ばれます。
名前の通り、まずは1つの方向へ深く進みます。行き止まりになったら、少し戻って別の道を調べます。
今回のグラフで、隣接リストの順番通りに探索すると、訪問順は次のようになります。
0 -> 1 -> 3 -> 4 -> 2 -> 5
DFSは「今いる頂点から行けるところへ先に進む」と考えると理解しやすいです。
BFSとは？
BFS(Breadth First Search)は、日本語では幅優先探索と呼ばれます。
DFSとは違い、開始地点から近い頂点を順番に見ていきます。距離が 0 の頂点、距離が 1 の頂点、距離が 2 の頂点、というように層を広げるイメージです。
今回のグラフでは、訪問順は次のようになります。
0 -> 1 -> 2 -> 3 -> 4 -> 5
BFSは、辺の重みがすべて同じグラフで最短距離を求めるときによく使います。
DFSとBFSの違い
一番大きな違いは、次に探索する頂点の管理方法です。
| 項目 | DFS | BFS |
|---|---|---|
| 日本語名 | 深さ優先探索 | 幅優先探索 |
| 進み方 | 進めるだけ深く進む | 近い頂点から順番に進む |
| 使うデータ構造 | 再帰、またはスタック | キュー |
| 得意なこと | 全探索、連結成分、木の探索 | 最短距離、階層ごとの探索 |
| 注意点 | 再帰が深いとスタックオーバーフローに注意 | 訪問済み管理を忘れると同じ頂点を何度も入れる |
迷ったときは、まず次のように考えると選びやすいです。
- 経路を深く試したいなら DFS
- 開始地点からの近さを知りたいなら BFS
C#での実装
DFSとBFSを同じグラフで実行するコードです。
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
var graph = BuildGraph(6, new (int, int)[]
{
(0, 1),
(0, 2),
(1, 3),
(1, 4),
(2, 5),
});
Console.WriteLine("DFS: " + string.Join(" -> ", Dfs(graph, 0)));
Console.WriteLine("BFS: " + string.Join(" -> ", Bfs(graph, 0)));
}
static List<int>[] BuildGraph(int n, (int from, int to)[] edges)
{
var graph = new List<int>[n];
for (int i = 0; i < n; i++)
{
graph[i] = new List<int>();
}
foreach (var (from, to) in edges)
{
graph[from].Add(to);
graph[to].Add(from);
}
return graph;
}
static List<int> Dfs(List<int>[] graph, int start)
{
var visited = new bool[graph.Length];
var order = new List<int>();
void Visit(int current)
{
visited[current] = true;
order.Add(current);
foreach (int next in graph[current])
{
if (!visited[next])
{
Visit(next);
}
}
}
Visit(start);
return order;
}
static List<int> Bfs(List<int>[] graph, int start)
{
var visited = new bool[graph.Length];
var order = new List<int>();
var queue = new Queue<int>();
visited[start] = true;
queue.Enqueue(start);
while (queue.Count > 0)
{
int current = queue.Dequeue();
order.Add(current);
foreach (int next in graph[current])
{
if (!visited[next])
{
visited[next] = true;
queue.Enqueue(next);
}
}
}
return order;
}
}
実行例
出力は次のようになります。
DFS: 0 -> 1 -> 3 -> 4 -> 2 -> 5
BFS: 0 -> 1 -> 2 -> 3 -> 4 -> 5
同じグラフでも、探索の順番が変わっていることがわかります。
DFSは 0 -> 1 -> 3 のように、まず深い方向へ進みます。
BFSは 0 -> 1 -> 2 のように、開始地点に近い頂点を先に見ます。
BFSで距離を求める
BFSは、開始地点から各頂点までの最短距離を求めるときにも使えます。
辺の重みがすべて同じなら、先に到達した経路が最短になります。
static int[] BfsDistance(List<int>[] graph, int start)
{
var distance = new int[graph.Length];
Array.Fill(distance, -1);
var queue = new Queue<int>();
distance[start] = 0;
queue.Enqueue(start);
while (queue.Count > 0)
{
int current = queue.Dequeue();
foreach (int next in graph[current])
{
if (distance[next] != -1)
{
continue;
}
distance[next] = distance[current] + 1;
queue.Enqueue(next);
}
}
return distance;
}
このように、distance[next] = distance[current] + 1 とすることで、開始地点からの距離を順番に埋められます。
AtCoderなどで「マス目の最短手数」や「辺の重みがないグラフの最短距離」を求める問題では、この形のBFSをよく使います。
計算量
頂点数を V、辺の数を E とします。
DFSもBFSも、各頂点と各辺を基本的に1回ずつ確認します。
| アルゴリズム | 時間計算量 | 空間計算量 |
|---|---|---|
| DFS | O(V + E) | O(V) |
| BFS | O(V + E) | O(V) |
計算量は同じですが、使う場面が違います。
DFSは深い探索や全探索に向いています。BFSは近い順に調べたいときや、最短距離を求めたいときに向いています。
つまずきやすいポイント
訪問済み管理を忘れない
グラフには循環があることがあります。
たとえば 0 と 1 がつながっていると、0 -> 1 -> 0 -> 1 ... のように行ったり来たりしてしまいます。
そのため、DFSでもBFSでも visited や distance を使って、すでに見た頂点を管理します。
BFSではキューに入れる時点で訪問済みにする
BFSでは、頂点をキューに入れるタイミングで訪問済みにするのが基本です。
取り出したタイミングで訪問済みにすると、同じ頂点が複数回キューに入ることがあります。
重み付きグラフの最短距離にはBFSをそのまま使わない
BFSで最短距離が求められるのは、辺の重みがすべて同じ場合です。
辺ごとにコストが違う場合は、ダイクストラ法などを使います。
まとめ
DFSとBFSは、どちらもグラフや木を探索する基本アルゴリズムです。
- DFSは、深く進んでから戻る
- BFSは、近い頂点から順番に広げる
- DFSは再帰やスタックで実装する
- BFSはキューで実装する
- 辺の重みがない最短距離はBFSが使いやすい
最初は「DFSは深く、BFSは近い順」と覚えておくと、問題を見たときに使い分けやすくなります。
参考
- 『問題解決力を鍛える！アルゴリズムとデータ構造』
- AtCoder のグラフ探索・最短経路系の問題
もう少し深く学ぶなら
『アルゴリズム図鑑 増補改訂版』
深く進むDFSと近い頂点から調べるBFSを、探索順と使いどころの違いから整理したい人に向く一冊です。
Discussion