🤖
【C#アルゴリズム】深さ優先探索と幅優先探索について
はじめに
深さ優先探索と幅優先探索についてまとめました。
深さ優先探索（Depth First Search、DFS）は、グラフや木構造において、ノードを 深く探索する ことを繰り返す探索アルゴリズムです。幅優先探索（Breadth First Search, BFS）は、グラフや木構造において 浅い階層から順に探索 するアルゴリズムです。
深さ優先探索について
深さ優先探索の特徴
- 再帰 または スタック を利用します。
- グラフや木を 深く進んでから戻る という動作になります。
- 再帰を使う場合は、 関数呼び出しのスタック を活用します。
深さ優先探索のアルゴリズムの流れ
- 開始ノード から探索を始めます。
- 未訪問の隣接ノードに進みます。
- 進める限り進んだら、戻って別の未訪問ノードを探索します。
- 全てのノードが訪問済みになったら終了します。
深さ優先探索のコード例
以下のコードは、再帰 を用いた深さ優先探索です。入力や出力の操作は省略しています。
- グラフは隣接リスト で表現します。
- 再帰 を用いて探索します。
-
訪問済みのノード管理 を
bool[] visitedで行います。
using System;
using System.Collections.Generic;
class Program
{
static void DFS(List<int>[] graph, bool[] visited, int current)
{
// 現在のノードを訪問済みとする
visited[current] = true;
// 現在のノードを処理（ここでは表示する例）
Console.WriteLine($"Visited Node: {current}");
// 隣接するノードを探索
foreach (int neighbor in graph[current])
{
if (!visited[neighbor])
{
DFS(graph, visited, neighbor); // 再帰的に探索
}
}
}
static void Main()
{
int N = 6; // ノードの数
List<int>[] graph = new List<int>[N];
// 隣接リストの初期化
for (int i = 0; i < N; i++)
{
graph[i] = new List<int>();
}
// グラフの辺を追加 (例: 無向グラフ)
graph[0].Add(1); graph[1].Add(0);
graph[0].Add(2); graph[2].Add(0);
graph[1].Add(3); graph[3].Add(1);
graph[1].Add(4); graph[4].Add(1);
graph[2].Add(5); graph[5].Add(2);
bool[] visited = new bool[N]; // 訪問済みの管理
int startNode = 0; // 開始ノード
// 深さ優先探索の実行
DFS(graph, visited, startNode);
}
}
コードの解説
-
隣接リストの準備
- グラフは
List<int>[] graphで表現し、各ノードに隣接するノードを追加します。 - 無向グラフの場合、
aとbの間に辺があれば両方に追加します。
- グラフは
-
DFS関数-
graph: 隣接リストのグラフ -
visited: 訪問済みのノードを記録する配列 -
current: 現在のノード - 現在のノードを訪問済みにし、隣接する未訪問ノードに対して再帰的に
DFSを呼び出します。
-
-
Main関数- ノード数
Nと辺の情報を基にグラフを作成します。 - 訪問済み配列
visitedを初期化します。 - 開始ノードから
DFSを実行します。
- ノード数
-
実行結果
入力グラフに対してノードが 深さ優先で探索 され、各ノードの訪問が順に出力されます。
実行イメージ
与えられたグラフの構造:
0
/ \
1 2
/ \ \
3 4 5
出力結果（訪問順）:
Visited Node: 0
Visited Node: 1
Visited Node: 3
Visited Node: 4
Visited Node: 2
Visited Node: 5
非再帰（スタックを使う）版のDFS
再帰を使わずに、明示的なスタックを用いて実装する場合のコードは以下の通りです：
using System;
using System.Collections.Generic;
class Program
{
static void DFS_Stack(List<int>[] graph, int startNode)
{
bool[] visited = new bool[graph.Length];
Stack<int> stack = new Stack<int>();
stack.Push(startNode);
while (stack.Count > 0)
{
int current = stack.Pop();
if (visited[current])
continue;
visited[current] = true;
Console.WriteLine($"Visited Node: {current}");
foreach (int neighbor in graph[current])
{
if (!visited[neighbor])
{
stack.Push(neighbor);
}
}
}
}
static void Main()
{
int N = 6;
List<int>[] graph = new List<int>[N];
for (int i = 0; i < N; i++)
{
graph[i] = new List<int>();
}
graph[0].Add(1); graph[1].Add(0);
graph[0].Add(2); graph[2].Add(0);
graph[1].Add(3); graph[3].Add(1);
graph[1].Add(4); graph[4].Add(1);
graph[2].Add(5); graph[5].Add(2);
int startNode = 0;
DFS_Stack(graph, startNode);
}
}
- 再帰版: 関数呼び出しのスタックを利用して実装。
-
非再帰版: 明示的に
Stackを使用して実装。
幅優先探索について
幅優先探索の特徴
- キュー（FIFO）を使って実装します。
- 訪問済み管理 を行わないと、無限ループする可能性があります。
- 最短距離 を求める場合に使われることが多いです。
- 深さ優先探索（DFS）とは異なり、ノードを 階層ごと に探索します。
幅優先探索のアルゴリズムの流れ
- 開始ノード をキューに追加し、訪問済みに設定します。
- キューからノードを取り出し、そのノードに隣接する 未訪問のノード をすべてキューに追加します。
- キューが空になるまでこの操作を繰り返します。
- すべてのノードが訪問済みになったら終了します。
幅優先探索のコード例
以下のコードは、キュー を用いた幅優先探索の基本的な実装です。
- グラフは隣接リスト で表現します。
- キュー を使って探索します。
-
訪問済みのノード管理 を
bool[] visitedで行います。
using System;
using System.Collections.Generic;
class Program
{
static void BFS(List<int>[] graph, int startNode)
{
bool[] visited = new bool[graph.Length]; // 訪問済みを管理する配列
Queue<int> queue = new Queue<int>(); // 探索に使うキュー
// 開始ノードをキューに追加し、訪問済みにする
queue.Enqueue(startNode);
visited[startNode] = true;
while (queue.Count > 0)
{
int current = queue.Dequeue(); // キューの先頭からノードを取り出す
// 現在のノードを処理（ここでは表示する例）
Console.WriteLine($"Visited Node: {current}");
// 隣接するノードを探索
foreach (int neighbor in graph[current])
{
if (!visited[neighbor])
{
queue.Enqueue(neighbor); // 未訪問ならキューに追加
visited[neighbor] = true; // 訪問済みにする
}
}
}
}
static void Main()
{
int N = 6; // ノード数
List<int>[] graph = new List<int>[N];
// 隣接リストの初期化
for (int i = 0; i < N; i++)
{
graph[i] = new List<int>();
}
// グラフの辺を追加 (例: 無向グラフ)
graph[0].Add(1); graph[1].Add(0);
graph[0].Add(2); graph[2].Add(0);
graph[1].Add(3); graph[3].Add(1);
graph[1].Add(4); graph[4].Add(1);
graph[2].Add(5); graph[5].Add(2);
int startNode = 0; // 探索の開始ノード
// 幅優先探索の実行
BFS(graph, startNode);
}
}
コードの解説
-
隣接リストの準備
- グラフは
List<int>[] graphで表現し、各ノードに隣接するノードを追加します。 - 無向グラフの場合、
aとbの間に辺があれば両方に追加します。
- グラフは
-
BFS関数-
graph: 隣接リストのグラフ -
startNode: 探索の開始ノード - キュー を使ってノードを順に探索し、訪問済みのノードを記録します。
- キューからノードを取り出し、そのノードに隣接する未訪問ノードをキューに追加します。
-
-
Main関数- ノード数
Nと辺の情報を基にグラフを作成します。 - 開始ノードから
BFSを実行します。
- ノード数
-
出力結果
探索の順番でノードが表示されます。
実行イメージ
与えられたグラフの構造:
0
/ \
1 2
/ \ \
3 4 5
出力結果（訪問順）:
Visited Node: 0
Visited Node: 1
Visited Node: 2
Visited Node: 3
Visited Node: 4
Visited Node: 5
深さ優先探索と幅優先探索の比較
- BFS は キュー を使い、浅い階層から順にノードを探索します。
- 最短経路を求める問題でよく利用されます。
- グラフや木の探索では、BFS と DFS を問題に応じて使い分けることが重要です。
以下に、幅優先探索（BFS） と 深さ優先探索（DFS） の違いを表形式でまとめます。
| 項目 | 幅優先探索（BFS） | 深さ優先探索（DFS） |
|---|---|---|
| データ構造 | キュー（FIFO：先入れ先出し） | スタック（LIFO：後入れ先出し） または再帰 |
| 探索順序 | 浅い階層から順番に探索 | 深い階層まで進んでから戻る |
| 最短経路 | 辺の重みが等しい場合は最短経路を発見 | 最短経路は保証されない |
| メモリの使用量 | 幅が広いグラフでメモリ消費が増大 | 深さの深いグラフでスタック消費が増大 |
| 実装方法 | キューを明示的に使用して実装 | 再帰またはスタックで実装 |
| 適した用途 | 最短経路の発見、レベル単位の探索 | 経路全探索、木構造の解析 |
| 動作例 | 同じ階層（レベル）を先に探索 | 一つの経路を進めるだけ進んでから戻る |
Discussion