グラフの深さ優先探索（DFS）とは？仕組みとC++実装例をわかりやすく解説

深さ優先探索（DFS：Depth First Search）は、グラフを巡回（トラバース）するための代表的なアルゴリズムです。開始頂点を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 0 1
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++による実装例

以下は、上記のアルゴリズムをC++で実装したサンプルコードです。開始頂点は C に設定しています。

#include<iostream>
#include<stack>
using namespace std;
#define NODE 6
typedef struct node{
   int val;
   int state; //状態（0：未訪問、1：訪問済み）
}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 から探索を始めると、隣接頂点を優先的に深くたどることで C → F → E → B → D → A の順にグラフ全体が巡回されます。DFSは木構造や迷路の探索、連結成分の検出など、さまざまな場面で応用される基本的かつ重要なアルゴリズムです。