アルゴリズム

C言語による深さ優先探索の実装解説：スタックと再帰を用いたグラフ探索アルゴリズム

2025-01-17更新日: 2025-01-17

この記事ではC言語を使った深さ優先探索の実装方法について解説します。

スタックや再帰を用いてグラフ内のノードを効率的に探索する手法や具体的なコーディング例を紹介し、シンプルで分かりやすい実践内容となっています。

目次から探す

深さ優先探索の基本
- 深さ優先探索とは
- グラフ構造と探索対象の考え方
スタックを用いた実装手法
再帰を用いた実装手法
スタックと再帰の実装比較
- メリット・デメリットの比較
- 利用シーンと選択基準
実装時の留意点
- テスト方法とデバッグのコツ
- コードの保守・拡張性への配慮
まとめ

深さ優先探索の基本

深さ優先探索とは

深さ優先探索(Depth First Search, DFS)は、グラフや木構造の各頂点を辿るアルゴリズムです。

ある頂点から隣接する頂点に進み、これ以上進めなくなると、前の頂点に戻して未訪問の頂点を辿るという方法を取ります。

探索の進み方は以下のように表せます。

$Missing \begin{cases} or extra \end{cases}$

このため、探索経路ができるだけ深くなるように進むことが特徴であり、全体の探索経路を明示的に管理しなくても自動的に辿る順序が決定される仕組みになっています。

グラフ構造と探索対象の考え方

グラフ構造は、頂点とそれらを結ぶ辺で構成されます。

C言語ではグラフの表現として、一般的に以下の方法が用いられます。

隣接行列

頂点数が少ない場合、\texttt{int graph[MAX_VERTICES][MAX_VERTICES]}のような2次元配列を用いて、頂点間の接続有無を表現します。

隣接リスト

頂点数が多く、疎なグラフの場合、各頂点に対する隣接リストを作成し、動的なメモリ管理と組み合わせて実装することが多いです。

DFSでは、探索の起点となる頂点から順次、隣接する未訪問の頂点に進んでいき、全頂点の訪問を目指します。

再帰またはスタックといった手法を用いることで、どちらの表現方法とも相性がよく、柔軟な探索が可能です。

スタックを用いた実装手法

スタックの基本構造と操作方法

スタックは「後入れ先出し(LIFO)」のデータ構造です。

C言語では配列とポインタを用いて簡単に実装できます。

スタックの基本動作としては、下記の操作が含まれます。

push

要素をスタックに追加する操作。

pop

スタックの先頭から要素を取り出す操作。

これらの操作は、探索時に現在の探索経路を管理するのに役立ちます。

スタックがあれば、再帰を使わずに明示的に戻るポイント管理を実現できます。

スタックを用いたDFSアルゴリズムの流れ

スタックを使用したDFSの基本的な流れは次の通りです。

初めに、開始頂点をスタックに入れます。
スタックが空でない限り、以下の処理を行います。

スタックから頂点を取り出し、未訪問であればその頂点を訪問済みにします。
取り出した頂点に隣接する頂点の中から、未訪問のものをスタックに追加します。

このような手法で、グラフ全体を効率的に探索することが可能です。

コード例と動作解説

以下に、スタックを用いたDFSのサンプルコードを示します。

コード中に簡潔なコメントを含めているので、アルゴリズムの流れが理解しやすくなっています。

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 5   // 頂点数
#define STACK_SIZE 100   // スタックサイズ
// 隣接行列によるグラフ表現
int graph[MAX_VERTICES][MAX_VERTICES] = {
    {0, 1, 1, 0, 0},
    {0, 0, 1, 1, 0},
    {0, 0, 0, 1, 1},
    {0, 0, 0, 0, 1},
    {0, 0, 0, 0, 0}
};
int visited[MAX_VERTICES] = {0};  // 訪問済み管理
// スタックの定義
typedef struct {
    int data[STACK_SIZE];
    int top;
} Stack;
// スタックの初期化
void initStack(Stack *stack) {
    stack->top = -1;
}
// スタックが空かの判定
int isEmpty(Stack *stack) {
    return stack->top == -1;
}
// スタックに要素を追加
int push(Stack *stack, int val) {
    if (stack->top >= STACK_SIZE - 1) {
        // スタックオーバーフロー
        return -1;
    }
    stack->data[++(stack->top)] = val;
    return 0;
}
// スタックから要素を取り出す
int pop(Stack *stack, int *val) {
    if (isEmpty(stack)) {
        // スタックアンダーフロー
        return -1;
    }
    *val = stack->data[(stack->top)--];
    return 0;
}
// スタックを用いたDFSの実装
void dfsStack(int start) {
    Stack stack;
    initStack(&stack);
    push(&stack, start);
    while (!isEmpty(&stack)) {
        int vertex;
        pop(&stack, &vertex);
        if (!visited[vertex]) {
            printf("Visited %d\n", vertex);
            visited[vertex] = 1;
        }
        // 隣接頂点を逆順でスタックに追加
        for (int i = MAX_VERTICES - 1; i >= 0; i--) {
            if (graph[vertex][i] && !visited[i]) {
                push(&stack, i);
            }
        }
    }
}
int main() {
    // 頂点0を起点に探索
    dfsStack(0);
    return 0;
}

Visited 0
Visited 2
Visited 4
Visited 3
Visited 1

上記サンプルコードでは、隣接行列で表現されたグラフを探索対象としており、スタック操作で探索経路を管理しています。

スタックに格納される頂点順を逆にすることで、より自然な順序で探索が進むように工夫しています。

エラー処理と注意点

スタックを用いる場合、スタックオーバーフローやアンダーフローといったエラーに注意が必要です。

特にグラフのサイズや接続性によっては、スタックのサイズを十分に確保する必要があります。

また、誤って同じ頂点を複数回訪問しないよう、必ず訪問管理用の配列(この例ではvisited)を用いて、重複処理を避ける工夫が求められます。

再帰を用いた実装手法

再帰呼び出しの仕組み

再帰を利用したDFSでは、関数自身を呼び出すことで探索経路を管理します。

再帰呼び出しは、内部で呼び出し履歴をスタック構造を用いて自動的に管理するため、スタック操作を明示的に記述する必要がありません。

関数が呼び出された際に、引数として渡された頂点から隣接頂点に対して再帰的に探索が行われます。

再帰を用いたDFSアルゴリズムの流れ

再帰によるDFSの手順は下記の通りです。

渡された頂点が未訪問であれば訪問し、頂点を処理します。
隣接する各頂点に対し、未訪問であればその頂点を起点として再帰的に探索を行います。

この流れは、再帰関数の呼び出しにより自動的にスタック構造が形成されるため、コードがシンプルになりやすいです。

コード例と動作解説

以下に再帰を用いたDFSのサンプルコードを示します。

訪問済みのチェックを行いながら、グラフ全体を順次探索する実装例です。

#include <stdio.h>
#define MAX_VERTICES 5
// 隣接行列によるグラフ表現
int graph[MAX_VERTICES][MAX_VERTICES] = {
    {0, 1, 1, 0, 0},
    {0, 0, 1, 1, 0},
    {0, 0, 0, 1, 1},
    {0, 0, 0, 0, 1},
    {0, 0, 0, 0, 0}
};
int visited[MAX_VERTICES] = {0};
// 再帰を用いたDFSの実装
void dfsRecursion(int vertex) {
    if (visited[vertex])
        return;
    printf("Visited %d\n", vertex);
    visited[vertex] = 1;
    // 隣接頂点を順に探索
    for (int i = 0; i < MAX_VERTICES; i++) {
        if (graph[vertex][i] && !visited[i]) {
            dfsRecursion(i);
        }
    }
}
int main() {
    // 頂点0を起点に探索
    dfsRecursion(0);
    return 0;
}

Visited 0
Visited 1
Visited 3
Visited 4
Visited 2

このサンプルコードでは、頂点の訪問順序が再帰呼び出しにより決定されます。

関数内部で訪問済みのチェックを行うことで、無限再帰を防止し、すべての頂点が一度だけ訪問されるように工夫しています。

メモリ管理と最適化のポイント

再帰を用いた実装はコードがシンプルになりますが、再帰呼び出しの深さが増えると、呼び出しスタックが大きくなりすぎる恐れがあります。

グラフが非常に深い場合、スタックオーバーフローが発生する可能性があります。

そのため、再帰深度に依存しない実装が求められる場合は、スタックによる実装も検討することが推奨されます。

また、コンパイラの最適化(例えば尾再帰最適化)が適用できる場合には、適切なコード設計を行うことが望ましいです。

スタックと再帰の実装比較

メリット・デメリットの比較

スタックを用いる実装と再帰を用いる実装の主な比較ポイントは以下の通りです。

スタックを用いた実装
- メリット: 呼び出し制限に左右されず、明示的にデータ構造を管理できるため、再帰深度に制限がある環境でも安全に利用できる。
- デメリット: スタック操作の実装が必要となり、コードが冗長になりがちである。
再帰を用いた実装
- メリット: コードがシンプルで読みやすく、直感的に探索の流れを理解しやすい。
- デメリット: 再帰の深さによってはスタックオーバーフローのリスクがある。また、関数呼び出しによるオーバーヘッドが増加する可能性がある。