アルゴリズム

[C言語] 深さ優先探索(DFS)を実装する方法

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

C言語で深さ優先探索(DFS)を実装するには、再帰またはスタックを使用します。

再帰的な方法では、まず訪問するノードを記録し、次にそのノードに隣接する未訪問のノードに対して再帰的にDFSを呼び出します。

スタックを使う場合は、初期ノードをスタックにプッシュし、スタックが空になるまでループして、ノードをポップして処理し、隣接する未訪問ノードをスタックにプッシュします。

目次から探す

深さ優先探索(DFS)とは
DFSのアルゴリズムの概要
C言語でのDFS実装
完成したサンプルコード
- コードの説明
- 実行結果
DFSの応用例
DFS実装時の注意点
DFSの最適化
まとめ

深さ優先探索(DFS)とは

深さ優先探索(DFS)は、グラフや木構造を探索するためのアルゴリズムの一つです。

DFSは、あるノードから出発し、可能な限り深く探索を進め、行き止まりに達したらバックトラックして別の経路を探索します。

この方法により、全てのノードを訪問することができます。

DFSの基本

DFSは、以下のような基本的な流れで動作します。

スタートノードを訪問する。
訪問したノードを記録する。
隣接する未訪問のノードがあれば、そのノードに移動し、再帰的に探索を続ける。
行き止まりに達したら、前のノードに戻り、別の経路を探索する。

このプロセスを繰り返すことで、全てのノードを訪問します。

幅優先探索(BFS)との違い

DFSと幅優先探索(BFS)は、どちらもグラフを探索する手法ですが、探索の順序が異なります。

特徴	深さ優先探索 (DFS)	幅優先探索 (BFS)
探索方法	深く進む	幅広く進む
使用するデータ構造	スタック	キュー
訪問順序	深さ優先	幅優先
メモリ使用量	少ない場合が多い	多い場合が多い

DFSは、特定の経路を深く探索するのに適しており、BFSは最短経路を見つけるのに適しています。

DFSが適している問題

DFSは以下のような問題に適しています。

迷路探索
トポロジカルソート
強連結成分の発見
パズルの解法
グラフの連結性の確認

これらの問題では、DFSの特性を活かして効率的に解決することができます。

DFSのメリットとデメリット

DFSにはいくつかのメリットとデメリットがあります。

メリット	デメリット
実装が簡単で直感的	最悪の場合、スタックオーバーフローのリスクがある
メモリ使用量が少ない場合が多い	最短経路を見つけることができない
特定の問題に対して効率的に動作する	無限ループに陥る可能性がある

DFSは、特定の条件下で非常に効果的ですが、使用する際にはその特性を理解しておくことが重要です。

DFSのアルゴリズムの概要

深さ優先探索(DFS)のアルゴリズムは、再帰またはスタックを使用して実装されます。

ここでは、DFSの基本的な流れと、グラフの表現方法、訪問済みノードの管理方法について詳しく説明します。

再帰を使ったDFSの流れ

再帰を使用したDFSの流れは以下の通りです。

現在のノードを訪問する。
訪問済みノードとして記録する。
隣接する未訪問のノードに対して、再帰的にDFSを呼び出す。

再帰を使用することで、コードがシンプルになり、自然な形で深さ優先の探索が実現できます。

スタックを使ったDFSの流れ

スタックを使用したDFSの流れは以下のようになります。

スタックにスタートノードをプッシュする。
スタックが空でない限り、以下を繰り返す。

スタックのトップノードをポップする。
訪問済みノードとして記録する。
隣接する未訪問のノードをスタックにプッシュする。

スタックを使用することで、再帰を使わずにDFSを実装できます。

これにより、スタックオーバーフローのリスクを回避できます。

グラフの表現方法

DFSを実装するためには、グラフを適切に表現する必要があります。

主な表現方法には、隣接リストと隣接行列があります。

隣接リスト

隣接リストは、各ノードに対してそのノードに隣接するノードのリストを持つデータ構造です。

メモリ効率が良く、スパースなグラフに適しています。

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;
typedef struct Graph {
    int numVertices;
    Node** adjLists;
} Graph;

隣接行列

隣接行列は、ノード間の接続を行列で表現する方法です。

行列の要素が1であれば接続されており、0であれば接続されていないことを示します。

密なグラフに適しています。

typedef struct Graph {
    int numVertices;
    int** adjMatrix;
} Graph;

訪問済みノードの管理方法

DFSでは、訪問済みノードを管理することが重要です。

これにより、無限ループを防ぎ、効率的に探索を行うことができます。

訪問済みノードは、配列やセットを使用して管理します。

int visited[MAX_VERTICES]; // 訪問済みノードの配列

DFSを実行する際には、ノードを訪問するたびにこの配列を更新し、次に訪問するノードを決定する際に参照します。

これにより、既に訪問したノードを再度訪問することを防ぎます。

C言語でのDFS実装

C言語で深さ優先探索(DFS)を実装する方法について、再帰とスタックを使用した実装、隣接リストと隣接行列を使ったグラフの実装、そして訪問済みノードの管理方法について詳しく説明します。

再帰を使ったDFSの実装

再帰を使用したDFSの実装は、以下のようになります。

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
int visited[MAX_VERTICES]; // 訪問済みノードの配列
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;
typedef struct Graph {
    int numVertices;
    Node** adjLists;
} Graph;
// 再帰的DFS関数
void DFS(Graph* graph, int vertex) {
    visited[vertex] = 1; // ノードを訪問済みとしてマーク
    printf("%d ", vertex); // 訪問したノードを出力
    Node* temp = graph->adjLists[vertex];
    while (temp) {
        int connectedVertex = temp->vertex;
        if (!visited[connectedVertex]) {
            DFS(graph, connectedVertex); // 再帰的に呼び出し
        }
        temp = temp->next;
    }
}
int main() {
    // グラフの初期化とDFSの呼び出しは省略
    return 0;
}

このコードでは、再帰的にDFSを実行し、訪問したノードを出力します。

スタックを使ったDFSの実装

スタックを使用したDFSの実装は、以下のようになります。

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
int visited[MAX_VERTICES]; // 訪問済みノードの配列
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;
typedef struct Graph {
    int numVertices;
    Node** adjLists;
} Graph;
typedef struct Stack {
    int items[MAX_VERTICES];
    int top;
} Stack;
// スタックの初期化
void initStack(Stack* s) {
    s->top = -1;
}
// スタックが空かどうかを確認
int isEmpty(Stack* s) {
    return s->top == -1;
}
// スタックにアイテムをプッシュ
void push(Stack* s, int item) {
    s->items[++(s->top)] = item;
}
// スタックからアイテムをポップ
int pop(Stack* s) {
    return s->items[(s->top)--];
}
// スタックを使ったDFS関数
void DFS(Graph* graph, int startVertex) {
    Stack s;
    initStack(&s);
    push(&s, startVertex);
    visited[startVertex] = 1;
    while (!isEmpty(&s)) {
        int vertex = pop(&s);
        printf("%d ", vertex); // 訪問したノードを出力
        Node* temp = graph->adjLists[vertex];
        while (temp) {
            int connectedVertex = temp->vertex;
            if (!visited[connectedVertex]) {
                push(&s, connectedVertex); // スタックにプッシュ
                visited[connectedVertex] = 1; // 訪問済みとしてマーク
            }
            temp = temp->next;
        }
    }
}
int main() {
    // グラフの初期化とDFSの呼び出しは省略
    return 0;
}

このコードでは、スタックを使用してDFSを実行し、訪問したノードを出力します。

隣接リストを使ったグラフの実装

隣接リストを使ったグラフの実装は以下のようになります。

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;
typedef struct Graph {
    int numVertices;
    Node** adjLists;
} Graph;
// グラフの初期化
Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(Node*));
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }
    return graph;
}
// エッジの追加
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
    // 無向グラフの場合、逆方向のエッジも追加
    newNode = malloc(sizeof(Node));
    newNode->vertex = src;
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

このコードでは、隣接リストを使用してグラフを構築し、エッジを追加する関数を定義しています。

隣接行列を使ったグラフの実装

隣接行列を使ったグラフの実装は以下のようになります。

#include <stdio.h>
#include <stdlib.h>
typedef struct Graph {
    int numVertices;
    int** adjMatrix;
} Graph;
// グラフの初期化
Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjMatrix = malloc(vertices * sizeof(int*));
    for (int i = 0; i < vertices; i++) {
        graph->adjMatrix[i] = malloc(vertices * sizeof(int));
        for (int j = 0; j < vertices; j++) {
            graph->adjMatrix[i][j] = 0; // 初期化
        }
    }
    return graph;
}
// エッジの追加
void addEdge(Graph* graph, int src, int dest) {
    graph->adjMatrix[src][dest] = 1; // エッジを追加
    graph->adjMatrix[dest][src] = 1; // 無向グラフの場合
}

このコードでは、隣接行列を使用してグラフを構築し、エッジを追加する関数を定義しています。

訪問済みノードの管理方法の実装

訪問済みノードの管理は、配列を使用して行います。

以下のように、訪問済みノードを管理するための配列を初期化することができます。

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
int visited[MAX_VERTICES]; // 訪問済みノードの配列
// 訪問済みノードの初期化
void initVisited(int numVertices) {
    for (int i = 0; i < numVertices; i++) {
        visited[i] = 0; // すべてのノードを未訪問として初期化
    }
}

この関数を使用して、DFSを実行する前に訪問済みノードの配列を初期化します。

これにより、各ノードの訪問状態を正しく管理できます。

完成したサンプルコード

以下に、深さ優先探索(DFS)を実装したC言語の完成したサンプルコードを示します。

このコードでは、隣接リストを使用してグラフを表現し、再帰的およびスタックを使ったDFSの両方を実行できるようにしています。

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// ノードの構造体
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;
// グラフの構造体
typedef struct Graph {
    int numVertices;
    Node** adjLists;
} Graph;
// 訪問済みノードの配列
int visited[MAX_VERTICES];
// グラフの初期化
Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(Node*));
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }
    return graph;
}
// エッジの追加
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
    // 無向グラフの場合、逆方向のエッジも追加
    newNode = malloc(sizeof(Node));
    newNode->vertex = src;
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}
// 再帰的DFS関数
void DFSRecursive(Graph* graph, int vertex) {
    visited[vertex] = 1; // ノードを訪問済みとしてマーク
    printf("%d ", vertex); // 訪問したノードを出力
    Node* temp = graph->adjLists[vertex];
    while (temp) {
        int connectedVertex = temp->vertex;
        if (!visited[connectedVertex]) {
            DFSRecursive(graph, connectedVertex); // 再帰的に呼び出し
        }
        temp = temp->next;
    }
}
// スタックを使ったDFS関数
void DFSStack(Graph* graph, int startVertex) {
    int stack[MAX_VERTICES];
    int top = -1;
    stack[++top] = startVertex; // スタートノードをプッシュ
    visited[startVertex] = 1;
    while (top != -1) {
        int vertex = stack[top--]; // スタックからポップ
        printf("%d ", vertex); // 訪問したノードを出力
        Node* temp = graph->adjLists[vertex];
        while (temp) {
            int connectedVertex = temp->vertex;
            if (!visited[connectedVertex]) {
                stack[++top] = connectedVertex; // スタックにプッシュ
                visited[connectedVertex] = 1; // 訪問済みとしてマーク
            }
            temp = temp->next;
        }
    }
}
// 訪問済みノードの初期化
void initVisited(int numVertices) {
    for (int i = 0; i < numVertices; i++) {
        visited[i] = 0; // すべてのノードを未訪問として初期化
    }
}
int main() {
    Graph* graph = createGraph(5); // 5つのノードを持つグラフを作成
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 4);
    printf("再帰的DFSの結果: ");
    initVisited(graph->numVertices); // 訪問済みノードの初期化
    DFSRecursive(graph, 0); // ノード0からDFSを開始
    printf("\n");
    printf("スタックを使ったDFSの結果: ");
    initVisited(graph->numVertices); // 訪問済みノードの初期化
    DFSStack(graph, 0); // ノード0からDFSを開始
    printf("\n");
    return 0;
}

コードの説明

グラフの初期化: createGraph関数でグラフを初期化し、ノード数を指定します。
エッジの追加: addEdge関数でノード間のエッジを追加します。

無向グラフとして実装されています。

再帰的DFS: DFSRecursive関数で再帰的にDFSを実行し、訪問したノードを出力します。
スタックを使ったDFS: DFSStack関数でスタックを使用してDFSを実行し、訪問したノードを出力します。
訪問済みノードの管理: initVisited関数で訪問済みノードの配列を初期化します。

実行結果

このプログラムを実行すると、再帰的DFSとスタックを使ったDFSの結果が出力されます。

例えば、以下のような出力が得られます。

再帰的DFSの結果: 0 2 4 1 3 
スタックを使ったDFSの結果: 0 1 3 4 2

このように、DFSの実装が正しく機能していることが確認できます。

DFSの応用例

深さ優先探索(DFS)は、さまざまな問題に応用できる強力なアルゴリズムです。

以下に、DFSの具体的な応用例をいくつか紹介します。

迷路探索

DFSは迷路探索において、スタート地点からゴール地点までの経路を見つけるために使用されます。

迷路をグラフとして表現し、各セルをノード、隣接するセルをエッジとして扱います。

DFSを用いることで、行き止まりに達した場合はバックトラックし、他の経路を探索することができます。

トポロジカルソート

トポロジカルソートは、有向非巡回グラフ(DAG)のノードを線形に並べる手法です。

DFSを使用して、各ノードを訪問し、訪問が完了したノードをスタックにプッシュします。

全てのノードの訪問が完了した後、スタックからノードを取り出すことで、トポロジカル順序を得ることができます。

強連結成分分解

強連結成分分解は、有向グラフの強連結成分を見つけるためにDFSを使用します。

KosarajuのアルゴリズムやTarjanのアルゴリズムでは、DFSを2回実行して、強連結成分を特定します。

最初のDFSでノードの訪問順序を記録し、次にグラフを反転させて再度DFSを実行することで、強連結成分を抽出します。

二部グラフ判定

二部グラフは、ノードを2つのグループに分け、同じグループ内のノード同士が接続されないグラフです。

DFSを使用して、ノードを訪問する際に色を付け、隣接するノードに異なる色を割り当てることで、二部グラフであるかどうかを判定できます。

もし隣接するノードが同じ色であれば、二部グラフではないことがわかります。

木の直径の計算

木の直径は、木の中で最も長いパスの長さを指します。

DFSを2回使用することで、木の直径を計算できます。

最初のDFSで任意のノードから最も遠いノードを見つけ、そのノードから再度DFSを実行して最も遠いノードまでの距離を計算します。

この距離が木の直径となります。

これらの応用例からもわかるように、DFSは多くの問題に対して効果的な解法を提供します。

特に、探索や構造の解析において、その特性を活かすことができます。

DFS実装時の注意点

深さ優先探索(DFS)を実装する際には、いくつかの注意点があります。

これらの注意点を理解し、適切に対処することで、より安全で効率的なアルゴリズムを実現できます。

再帰の深さ制限

再帰を使用したDFSでは、再帰の深さが制限されることがあります。

特に、非常に深い木やグラフを探索する場合、スタックの深さがプログラムの制限を超えると、スタックオーバーフローが発生する可能性があります。

これを防ぐためには、以下の対策が考えられます。

非再帰的な実装: スタックを使用して非再帰的にDFSを実装することで、再帰の深さ制限を回避できます。
再帰の深さを制限する: 再帰の深さを制限し、一定の深さに達した場合は探索を中止する方法もあります。

無限ループの防止

DFSを実行する際には、無限ループに陥るリスクがあります。

特に、グラフにサイクルが存在する場合、訪問済みノードを適切に管理しないと、同じノードを何度も訪問することになります。

無限ループを防ぐためには、以下の対策が重要です。

訪問済みノードの管理: 訪問済みノードを記録する配列やセットを使用し、既に訪問したノードを再度訪問しないようにします。
サイクルの検出: グラフの構造を事前に確認し、サイクルが存在する場合は適切な処理を行うことが重要です。

メモリ管理の重要性

DFSを実装する際には、メモリ管理が非常に重要です。

特に、動的にメモリを割り当てる場合、メモリリークが発生する可能性があります。

これを防ぐためには、以下の点に注意が必要です。

メモリの解放: 使用が終わったメモリは必ず解放し、メモリリークを防ぎます。

特に、ノードを追加した後は、不要になったノードを適切に解放することが重要です。

メモリの初期化: メモリを使用する前に、必ず初期化を行い、未初期化のメモリを参照しないようにします。

スタックオーバーフローの回避

再帰を使用したDFSでは、スタックオーバーフローが発生するリスクがあります。

これを回避するためには、以下の対策が有効です。

非再帰的な実装: スタックを使用して非再帰的にDFSを実装することで、スタックオーバーフローのリスクを回避できます。
再帰の深さを制限する: 再帰の深さを制限し、一定の深さに達した場合は探索を中止する方法もあります。
適切なデータ構造の選択: スタックのサイズを適切に設定し、必要に応じて動的にサイズを変更できるデータ構造を使用することも考慮します。

これらの注意点を考慮することで、DFSの実装がより安全で効率的になります。

特に、無限ループやスタックオーバーフローのリスクを理解し、適切に対処することが重要です。

DFSの最適化

深さ優先探索(DFS)を効率的に実行するためには、いくつかの最適化手法があります。

これらの手法を適用することで、探索の速度やメモリ使用量を改善することができます。

以下に、DFSの最適化手法を紹介します。

メモ化による再帰の最適化

メモ化は、再帰的なDFSにおいて、既に計算した結果を保存して再利用する手法です。

特に、同じノードに対して複数回の探索が行われる場合、メモ化を使用することで無駄な計算を省くことができます。

実装方法: 訪問済みノードの情報を配列やハッシュテーブルに保存し、再度訪問する際にはその情報を参照します。

これにより、同じノードに対する再帰呼び出しを避けることができます。

効果: メモ化を行うことで、計算量が大幅に削減され、特に大規模なグラフや木構造において、探索の効率が向上します。

グラフの前処理による効率化

グラフの前処理を行うことで、DFSの実行時に必要な情報を事前に準備し、探索を効率化することができます。

以下のような前処理が考えられます。

隣接リストの構築: グラフを隣接リストで表現することで、各ノードの隣接ノードへのアクセスを迅速に行えるようにします。

これにより、探索時のノードの取得が効率化されます。

ノードのソート: 隣接ノードを特定の順序(例えば、ノードのID順)でソートしておくことで、探索の際に特定の条件を満たすノードを優先的に訪問することができます。

これにより、特定の問題に対する探索の効率が向上します。

スタックを使った非再帰的実装の利点

スタックを使用した非再帰的なDFS実装には、いくつかの利点があります。

スタックオーバーフローの回避: 再帰を使用する場合、深い再帰呼び出しがスタックオーバーフローを引き起こす可能性がありますが、非再帰的な実装ではスタックのサイズを明示的に管理できるため、このリスクを回避できます。
メモリ使用の最適化: スタックを使用することで、必要なメモリを動的に管理でき、再帰的な呼び出しに比べてメモリの使用量を最適化できます。
探索の制御: 非再帰的な実装では、スタックを使用して探索の進行状況を明示的に管理できるため、探索の制御が容易になります。

これにより、特定の条件に基づいて探索を中断したり、別の経路を選択したりすることが可能です。

これらの最適化手法を適用することで、DFSの性能を向上させ、より効率的な探索を実現することができます。

特に、大規模なデータセットや複雑なグラフ構造を扱う際には、これらの最適化が重要となります。