C言語による深さ優先探索（DFS）の実装方法をわかりやすく解説

深さ優先探索（DFS）とは

深さ優先探索（Depth First Search：DFS）は、グラフ上のすべてのノードを訪問するためのアルゴリズムです。ある頂点から出発し、行き止まりに達するまで可能な限り深く探索を進め、その後ひとつ前の頂点に戻って未訪問の経路を順に調べていきます。また、2つのノード間にパス（経路）が存在するかどうかを判定することにも利用できます。

つまりDFSは、グラフや木構造を「深さ方向」に沿って探索していく手法です。

アルゴリズム

以下は、深さ優先探索（DFS）を実装するための基本的な手順です。

ステップ1 − 最初に、スタックは空の状態です。

ステップ2 − 訪問対象のノードがスタックに存在しない場合は、そのノードをスタックにプッシュし、「訪問済み」としてマークします。

ステップ3 − 現在のノードが検索条件に一致するかどうかを確認します。

    ステップ3.1 − 一致していれば、探索は完了です。

ステップ4 − 一致しない場合は、現在のノードに隣接するすべてのノードへ移動します。

    ステップ4.1 − それらのノードを任意の順序で訪問し、探索を続けます。

ステップ5 − 隣接するすべてのノードがすでに訪問済みであれば、そこは行き止まり（デッドエンド）です。

ステップ6 − 直前に訪問したノードへ戻り、直近のノードをスタックからポップします。

ステップ7 − すべてのノードが探索されたとき、または目的の答えが見つかった時点で、アルゴリズムは終了します。

C言語による実装プログラム

以下は、深さ優先探索（DFS）をC言語で実装したサンプルプログラムです。スタック操作用の関数（push / pop / peek）と、隣接行列によるグラフ表現を使用しています。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 5
void addVertex(char);
void addEdge(int,int );
void displayVertex(int);
void depthFirstSearch();
int getAdjUnvisitedVertex(int);
struct Vertex {
    char label;
    bool visited;
};
//stack variables
int stack[MAX];
int top = -1;
//graph variables
//array of vertices
struct Vertex* lstVertices[MAX];
//adjacency matrix
int adjMatrix[MAX][MAX];
//vertex count
int vertexCount = 0;
//stack functions
void push(int item) {
    stack[++top] = item;
}
int pop() {
    return stack[top--];
}
int peek() {
    return stack[top];
}
bool isStackEmpty() {
    return top == -1;
}
//graph functions
//add vertex to the vertex list
void addVertex(char label) {
    struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
    vertex->label = label;
    vertex->visited = false;
    lstVertices[vertexCount++] = vertex;
}
//add edge to edge array
void addEdge(int start,int end) {
    adjMatrix[start][end] = 1;
    adjMatrix[end][start] = 1;
}
//display the vertex
void displayVertex(int vertexIndex) {
    printf("%c ",lstVertices[vertexIndex]->label);
}
//get the adjacent unvisited vertex
int getAdjUnvisitedVertex(int vertexIndex) {
    int i;
    for(i = 0; i < vertexCount; i++) {
        if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false) {
            return i;
        }
    }
    return -1;
}
void depthFirstSearch() {
    int i;
    //mark first node as visited
    lstVertices[0]->visited = true;
    //display the vertex
    displayVertex(0);
    //push vertex index in stack
    push(0);
    while(!isStackEmpty()) {
        //get the unvisited vertex of vertex which is at top of the stack
        int unvisitedVertex = getAdjUnvisitedVertex(peek());
        //no adjacent vertex found
        if(unvisitedVertex == -1) {
            pop();
        } else {
            lstVertices[unvisitedVertex]->visited = true;
            displayVertex(unvisitedVertex);
            push(unvisitedVertex);
        }
    }
    //stack is empty, search is complete, reset the visited flag
    for(i = 0;i < vertexCount;i++) {
        lstVertices[i]->visited = false;
    }
}
int main() {
    int i, j;
    for(i = 0; i < MAX; i++) // set adjacency {
        for(j = 0; j < MAX; j++) // matrix to 0
            adjMatrix[i][j] = 0;
        addVertex('S'); // 0
        addVertex('A'); // 1
        addVertex('B'); // 2
        addVertex('C'); // 3
        addVertex('D'); // 4
        addEdge(0, 1); // S - A
        addEdge(0, 2); // S - B
        addEdge(0, 3); // S - C
        addEdge(1, 4); // A - D
        addEdge(2, 4); // B - D
        addEdge(3, 4); // C - D
        printf("Depth First Search: ");
        depthFirstSearch();
return 0;}

プログラムのポイント

• スタック構造：push・pop・peek の各関数により、探索の経路を管理します。
• 隣接行列：adjMatrix[i][j] が 1 の場合、頂点 i と j が辺で結ばれていることを示します。
• getAdjUnvisitedVertex：スタックの先頭にある頂点から、まだ訪問していない隣接頂点を探します。見つからなければ -1 を返し、バックトラック（ポップ）を行います。

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Depth First Search: S A D B C

この結果から、開始頂点 S から出発し、隣接する未訪問の頂点を優先的に深くたどりながら A → D → B → C の順に探索が進んでいることが確認できます。