【C言語】第8章第12回：深さ優先探索と幅優先探索
深さ優先探索（DFS）と幅優先探索（BFS）は、グラフ構造を探索するための基本的なアルゴリズムです。本記事では、DFSとBFSの基礎から応用までを学びます。
0. 記事の概要
この記事を読むメリット
- グラフ探索の基本を理解：DFSとBFSを学び、グラフ操作の基礎を身につけます。
- 実践的なスキルの習得：C言語でのDFSとBFSの実装方法を習得します。
- 応用力の向上：最短経路探索や連結成分の検出などへの応用が可能になります。
この記事で学べること
- DFSとBFSの基本概念と特性
- DFSとBFSの実装例とその動作
- DFSとBFSの応用例
1. 深さ優先探索（DFS）の基本
1.1 DFSとは？
深さ優先探索（Depth First Search, DFS）は、グラフまたはツリーの探索アルゴリズムで、最も深い部分まで探索した後、バックトラックして他の経路を探索します。
1.2 DFSの特性
- スタックを使用：再帰呼び出しや明示的なスタックを用いる
- すべての頂点を探索：未訪問の頂点を探索し、隣接する頂点を再帰的に訪問
1.3 DFSの実装例
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
// グラフの定義
typedef struct Graph {
int numVertices;
int adjMatrix[MAX][MAX];
} Graph;
// 初期化
void initGraph(Graph* graph, int vertices) {
graph->numVertices = vertices;
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
graph->adjMatrix[i][j] = 0;
}
}
}
// エッジを追加
void addEdge(Graph* graph, int src, int dest) {
graph->adjMatrix[src][dest] = 1;
graph->adjMatrix[dest][src] = 1; // 無向グラフの場合
}
// DFS
void DFS(Graph* graph, int vertex, int* visited) {
visited[vertex] = 1;
printf("%d ", vertex);
for (int i = 0; i < graph->numVertices; i++) {
if (graph->adjMatrix[vertex][i] && !visited[i]) {
DFS(graph, i, visited);
}
}
}
int main() {
Graph graph;
initGraph(&graph, 5);
addEdge(&graph, 0, 1);
addEdge(&graph, 0, 4);
addEdge(&graph, 1, 2);
addEdge(&graph, 1, 3);
addEdge(&graph, 1, 4);
int visited[MAX] = {0};
printf("DFS starting from vertex 0: ");
DFS(&graph, 0, visited);
return 0;
}
動作解説
- 初期化：グラフの頂点数と隣接行列を初期化します。
- エッジの追加：頂点間の接続を隣接行列に設定します。
- DFSの開始：再帰的に頂点を訪問し、未訪問の隣接頂点を探索します。
2. 幅優先探索（BFS）の基本
2.1 BFSとは？
幅優先探索（Breadth First Search, BFS）は、グラフまたはツリーの探索アルゴリズムで、各頂点をその隣接頂点すべてにわたって水平に探索します。
2.2 BFSの特性
- キューを使用：FIFO構造のキューで頂点を管理
- 最短経路探索に適応：非負重みグラフでの最短経路問題に利用可能
2.3 BFSの実装例
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
// BFS
void BFS(Graph* graph, int startVertex) {
int visited[MAX] = {0};
int queue[MAX];
int front = 0, rear = 0;
visited[startVertex] = 1;
queue[rear++] = startVertex;
while (front != rear) {
int currentVertex = queue[front++];
printf("%d ", currentVertex);
for (int i = 0; i < graph->numVertices; i++) {
if (graph->adjMatrix[currentVertex][i] && !visited[i]) {
visited[i] = 1;
queue[rear++] = i;
}
}
}
}
int main() {
Graph graph;
initGraph(&graph, 5);
addEdge(&graph, 0, 1);
addEdge(&graph, 0, 4);
addEdge(&graph, 1, 2);
addEdge(&graph, 1, 3);
addEdge(&graph, 1, 4);
printf("BFS starting from vertex 0: ");
BFS(&graph, 0);
return 0;
}
動作解説
- 初期化：訪問状況を記録する配列とキューを初期化します。
- 探索：現在の頂点から隣接頂点を探索し、未訪問の頂点をキューに追加します。
- 結果出力：キューから取り出した頂点を出力します。
3. 練習問題
以下の課題に挑戦して、DFSとBFSの理解を深めましょう。
- DFSを使用してグラフ内の連結成分を数えるプログラムを作成してください。
- BFSを使用してグラフの最短経路を計算するプログラムを作成してください。
- 有向グラフでDFSを使用してトポロジカルソートを実装してください。
4. 練習問題の解答と解説
問2の解答
// BFSを使用した最短経路計算
void shortestPathBFS(Graph* graph, int startVertex) {
int distance[MAX] = {0};
int queue[MAX];
int front = 0, rear = 0;
distance[startVertex] = 0;
queue[rear++] = startVertex;
while (front != rear) {
int currentVertex = queue[front++];
for (int i = 0; i < graph->numVertices; i++) {
if (graph->adjMatrix[currentVertex][i] && distance[i] == 0 && i != startVertex) {
distance[i] = distance[currentVertex] + 1;
queue[rear++] = i;
}
}
}
for (int i = 0; i < graph->numVertices; i++) {
printf("Distance from %d to %d: %d\n", startVertex, i, distance[i]);
}
}
このプログラムでは、BFSを使用して各頂点までの最短経路を計算します。
5. まとめ
本記事では、深さ優先探索（DFS）と幅優先探索（BFS）の基本概念と実装方法について学びました。次回はさらに高度なグラフアルゴリズムを掘り下げます。