C++でDFS（深さ優先探索）の探索手順を段階的に出力するプログラム

このチュートリアルでは、C++を用いて深さ優先探索（DFS）のトラバーサル手順を段階的に出力するプログラムについて解説します。

出力には、バックトラッキング（探索の巻き戻し）の過程も含め、DFSの実行中に発生するすべてのステップが表示されます。

DFSの実行中は、各ノードを走査すると同時に、親ノードと使用したエッジ（辺）の情報を記録していきます。走査の過程で隣接ノードがすでに訪問済みである場合、そのノードへの移動も含めて、DFSの各ステップとして出力することができます。

アルゴリズムの流れ

このプログラムの基本的な考え方は以下の通りです。

1. 各ノードの訪問状態を管理する配列を用意し、すべて「未訪問」で初期化します。
2. 開始ノード（ここではノード0）から探索を開始し、ノードを訪問するたびに訪問済みマークを付け、親ノードとのペアを経路情報として記録します。
3. 隣接する未訪問ノードが存在すれば、そこへ再帰的に移動します。
4. 未訪問の隣接ノードがなくなった場合は、記録しておいた経路情報を利用して親ノードへバックトラッキングします。これにより、探索が戻る過程も出力に反映されます。
5. すべてのノードが訪問済みになった時点で探索を終了します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
vector<int> adj[N];
//DFSトラバーサルの各ステップを出力する
void dfs_steps(int u, int node, bool visited[],
vector<pair<int, int>> path_used, int parent, int it){
   int c = 0;
   for (int i = 0; i < node; i++)
   if (visited[i])
      c++;
   if (c == node)
      return;
//ノードを訪問済みとしてマークする
   visited[u] = true;
   path_used.push_back({ parent, u });
   cout << u << " ";
   for (int x : adj[u]){
      if (!visited[x])
         dfs_steps(x, node, visited, path_used, u, it + 1);
   }
   for (auto y : path_used)
   if (y.second == u)
   dfs_steps(y.first, node, visited,
   path_used, u, it + 1);
}
void dfs(int node){
   bool visited[node];
   vector<pair<int, int>> path_used;
   for (int i = 0; i < node; i++)
   visited[i] = false;
   dfs_steps(0, node, visited, path_used, -1, 0);
   }
void add_edge(int u, int v){
   adj[u].push_back(v);
   adj[v].push_back(u);
}
int main(){
   int node = 11, edge = 13;
   add_edge(0, 1);
   add_edge(0, 2);
   add_edge(1, 5);
   add_edge(1, 6);
   add_edge(2, 4);
   add_edge(2, 9);
   add_edge(6, 7);
   add_edge(6, 8);
   add_edge(7, 8);
   add_edge(2, 3);
   add_edge(3, 9);
   add_edge(3, 10);
   add_edge(9, 10);
   dfs(node);
   return 0;
}

出力結果

0 1 5 1 6 7 8 7 6 1 0 2 4 2 9 3 10

出力の読み方

この出力からは、探索がノード0から始まり、1 → 5 と進んだ後、行き止まりに達したノード5からノード1へ戻り（バックトラッキング）、続いてノード6へ向かう様子が確認できます。さらに、7 → 8 と進んだ後は 8 → 7 → 6 → 1 → 0 と順に巻き戻り、その後ノード2の探索へ移行しています。

このように、DFSが実際にノードを訪れる順序だけでなく、探索が行き止まりに達した際に親ノードへ戻る過程まで、一連の流れとして出力できるのが本プログラムの特徴です。グラフの構造やDFSの動作を学習・デバッグする際に役立つ手法です。