グラフの深さ優先探索（DFS）とは？アルゴリズムとC++実装例を徹底解説

深さ優先探索（Depth-First Search：DFS）は、グラフを巡回するための基本的なアルゴリズムの一つです。開始頂点が1つ与えられると、隣接する頂点が見つかった時点でまずその頂点へ移動し、同じ要領でさらに奥へと探索を進めていきます。

DFSは、行き止まりに達してそれ以上進めなくなるまで可能な限り深く探索を進め、その後バックトラック（後戻り）を行いながら、未訪問の頂点につながる新しい経路を探していきます。

DFSを反復処理（イテレーティブ）な方法で実装する場合は、スタックというデータ構造を使用します。一方、再帰的に実装する場合は、関数呼び出し時に内部的にスタックが利用されるため、外部のスタックを明示的に用意する必要はありません。

入力と出力

入力：
グラフの隣接行列

        A B C D E F
    A   0 1 1 1 0 0
    B   1 0 0 1 1 0
    C   1 0 0 1 1 0
    D   1 1 1 0 1 1
    E   0 1 0 1 0 1
    F   0 0 1 1 1 0

出力：
DFS Traversal: C F E B D A

アルゴリズム

dfs(vertices, start)

入力： すべての頂点のリストと、開始ノード。

出力： グラフ内のすべてのノードを巡回します。

Begin
    最初にすべてのノードの状態を「未訪問」に設定する
    開始ノードをスタックにプッシュする

    スタックが空になるまで繰り返し：
        スタックから要素をポップし、u に代入する
        ノード u を表示する

        u が未訪問であれば：
            u を「訪問済み」としてマークする
            u に接続されているすべてのノード i に対して：
                i 番目の頂点が未訪問であれば：
                    i 番目の頂点をスタックにプッシュする
                    i 番目の頂点を「訪問済み」としてマークする
            繰り返し終了
    繰り返し終了
End

C++による実装例

以下は、隣接行列で表現されたグラフに対して、スタックを用いた反復方式のDFSを実装したC++のサンプルコードです。開始頂点は C に設定しています。

#include<iostream>
#include<stack>
using namespace std;
#define NODE 6

typedef struct node {
    int val;
    int state; // 訪問状態
}node;

int graph[NODE][NODE] = {
    {0, 1, 1, 1, 0, 0},
    {1, 0, 0, 1, 1, 0},
    {1, 0, 0, 1, 0, 1},
    {1, 1, 1, 0, 1, 1},
    {0, 1, 0, 1, 0, 1},
    {0, 0, 1, 1, 1, 0}
};

void dfs(node *vertex, node start) {
    node u;
    stack<node> myStack;

    for(int i = 0; i<NODE; i++) {
        vertex[i].state = 0;  // 未訪問に初期化
    }

    myStack.push(start);
    while(!myStack.empty()) {
        // ノードをポップして表示
        u = myStack.top();
        myStack.pop();
        cout << char(u.val+'A') << " ";

        if(u.state != 1) {
            // 訪問状態を更新
            u.state = 1;
            vertex[u.val].state = 1;

            for(int i = 0; i<NODE; i++) {
                if(graph[i][u.val]) {
                    if(vertex[i].state == 0) {
                        myStack.push(vertex[i]);
                        vertex[i].state = 1;
                    }
                }
            }
        }
    }
}

int main() {
    node vertices[NODE];
    node start;
    char s;

    for(int i = 0; i<NODE; i++) {
        vertices[i].val = i;
    }

    s = 'C';  // 開始頂点は C
    start.val = s-'A';
    cout << "DFS Traversal: ";
    dfs(vertices, start);
    cout << endl;
}

実行結果

DFS Traversal: C F E B D A

このように、開始頂点 C から探索を始めると、スタックの特性（LIFO：後入れ先出し）によって、まず可能な限り深い方向へ探索が進み、行き止まりに達すると順次バックトラックしながら残りの頂点を訪問します。その結果、「C → F → E → B → D → A」の順序でグラフ全体が巡回されます。