深さ優先探索(Depth First Search)

探索深さ優先探索, スタック, 再帰関数, 全探索

深さ優先探索とは、全探索アルゴリズムの一種です。木などのグラフやグラフと同一視できるものを探索する際に良く使われます。

幅優先探索(BFS)と似ていますが、深さ優先探索は末端に到達するまで「深く」探索してから、他のノードの探索を始めます。

英語では Depth First Search なので、DFSと略されることが多いです。

深さ優先探索
DFSの状態遷移の順番

アルゴリズム

深さ優先探索は、「とりあえずこれ以上進めなくなるまで探索したら、戻って別のルートで探索し直す」ようなアルゴリズムです。

実装方法としては、主に二種類あり、

  • スタックと呼ばれるデータ構造を用いた方法
  • 再帰関数を用いた方法

があります。

深さ優先探索ではスタックを用いて実装することができます(類似のアルゴリズムに幅優先探索がありますが、これはキューを用いて実装できます)。今まで通った場所をスタックに保存しながら進み、末端に到達したらスタックからどこに戻るかの情報を取出します。

もう一つの方法として、再帰関数を用いるやり方もあります。再帰関数を用いた全探索も、深さ優先探索の一種です。コンピュータ内部で関数を使う際に、スタックにデータを保存しておくため、このような動作になります。

スタックを用いると幅優先探索と同様に書けるというメリットがあり、逆に再帰関数を用いると簡単に実装することができるというメリットがあります。状況に合わせて、もしくは自分の好みで、どちらで実装するかを決めれば良いでしょう。

スタックを用いたアルゴリズム

  1. 始めの状態から遷移可能な状態を、全てスタックに入れる
  2. スタックに要素がなければ終了する
  3. 現在の状態から遷移可能な状態を、全てスタックに入れる
  4. スタックから1つ要素を取り出し、そこに状態を遷移させる
  5. 2.に戻る

幅優先探索のアルゴリズムのうち、キューをスタックに変更しただけで実装できます。

途中の状態は以下のようになります。

DFSの途中の状態
2まで探索したときの状態

再帰関数を用いたアルゴリズム

再帰関数を用いて深さ優先探索を実装できます。遷移可能な状態の個数分だけ、再帰関数を呼出して分岐させていきます。

プログラムは上から下へ実行されるため、再帰関数の呼び出され方がスタックを用いた時と同じ様になります。遷移可能な状態が無くなる(末端)まで、戻って別のノードを探索することはありません。

先程の図でいうと、状態1の時には、「状態2へ分岐する再帰関数」と「状態5へ分岐する再帰関数」を呼び出します。プログラムは上から下へ実行されるので、「状態2へ分岐する再帰関数」が先に実行され、これが終了するまで「状態5へ分岐する再帰関数」が呼び出されることはありません。

具体例で試してみる

以下のようなグラフについて深さ優先探索をしてみましょう。

0からスタートして、3にたどり着ければ 「OK」、たどり着けなければ「NO」を返すプログラムを幅優先探索で実装します。

隣接行列・隣接リスト(グラフを参照)のどちらでグラフを表現するのか、スタック・再帰関数のどちらで深さ優先探索を実装するのかで、やり方が色々と変わってきます。

Pythonの例

隣接行列・スタックを用いた実装は以下のようになります。

n = 4 # グラフの頂点数
# グラフの隣接行列
G = [[0,1,1,0],
     [0,0,0,1],
     [0,1,0,1],
     [0,0,0,0]]
destination = 3; # 3にたどり着くかを探索
stack = []      # リストをスタックのかわりに使用
used = [0]*n    # 探索済みかどうかを記録
stack.append(0) # 0からスタート
used[0] = 1
while len(stack) > 0:
  state = stack.pop()
  print("now state:",state) # 現在の状態を表示
  for next in range(n):
    if G[state][next] == 1 and used[next]!= 1: # next が移動可能な状態ならstackに加える
      used[next] = 1
      stack.append(next)
  if state==destination: # 最終状態にたどり着いたら終了
    break;
if used[destination]==1:
  print("OK")
else:
  print("NO")

出力は以下のようになります。

now state: 0
now state: 2
now state: 3
now state: 1
OK

C++の例

隣接リスト表現を用いて、スタックで実装すると以下のようになります。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N = 4;                // グラフの頂点数
    vector<vector<int>> G(N); // 隣接リスト表現によるグラフ
    G[0].emplace_back(1);
    G[0].emplace_back(2);
    G[1].emplace_back(3);
    G[2].emplace_back(1);
    G[2].emplace_back(3);
    int destination = 3; // 3にたどり着くかを探す
    stack<int> st;
    vector<int> used(N, 0); // 探索済みかどうかを記録
    st.emplace(0);          // 0から探索する
    used[0] = 1;
    while (st.size() != 0) {  // スタックの要素がなくなったら終了
        int state = st.top(); // 現在の状態
        cout << "now state: " << state << endl; // 現在の状態を表示
        if (state == destination) { // 目的地にたどり着いたので終了
            cout << "OK\n";
            return 0;
        }
        st.pop();
        for (auto next : G[state]) {
            if (used[next] != 1) { // 未探索の時のみ行う
                used[next] = 1;
                st.emplace(next); //次の状態をqueueへ格納
            }
        }
    }
    cout << "NO\n";
    return 0;
}

出力は先程と同じです。

隣接リスト・再帰関数を用いたC++での実装例は以下のようになります。

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> G;     // 隣接リスト表現によるグラフ
bool used[1000] = {false}; // 探索済みかどうかを記録
bool dfs(int state, int destination) { // state:現在の状態 destination:探す状態
    cout << "now state: " << state << endl; // 現在の状態を出力
    if (state == destination) { // destination までたどり着けば終了
        return true;
    }
    for (auto next : G[state]) { // 現在の状態から辿れる全ての状態について行う
        if (used[next] != true) { // 未探索の時のみ行う
            used[next] = true;
            if (dfs(next, destination)) { //目的地にたどり着いた時点で終了
                return true;
            }
        }
    }
    return false; // 探索して destination に到達しなかったので終了
}
int main() {
    // 適当な初期値を与える
    int N = 4; // グラフの頂点数
    vector<int> tmp;
    G.emplace_back(tmp);
    G[0].emplace_back(1);
    G[0].emplace_back(2);
    G.emplace_back(tmp);
    G[1].emplace_back(3);
    G.emplace_back(tmp);
    G[2].emplace_back(1);
    G[2].emplace_back(3);
    G.emplace_back(tmp);
    used[0] = true;
    if (dfs(0, 3)) { // 0からスタートして、3にたどり着くかみる
        cout << "OK\n";
    } else {
        cout << "NO\n";
    }
    return 0;
}

実際に問題を解いてみる

AtCoder ATC001 A – 深さ優先探索 を解いてみましょう。

問題概要

スタート( s )・ゴール( g )・道( . )・壁( # )で構成されたH行W列のマスについて、スタートから壁を通らずにゴールまでたどりつけるか判定してください。

考え方

スタートから深さ優先探索をすると、ゴールに到達するか判定することができます。

グラフではなく、マス目でできた迷路上の探索なので、先程の例とプログラムの書き方が少し違いますが、基本的なアルゴリズムの考え方は変わりません。

隣り合うマス目を、再帰関数で探索してください。このとき、既に探索したことのあるマス目は探索しないようにしないと、無限ループに陥ってしまいます。

プログラム例

再帰関数での例を以下に示します。スタックを用いることでも同様に探索することができます。

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n); i >= 0; i--)
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
int H, W;
char maze[550][550]; // 迷路の内容を保存する配列
bool used[550][550]; // 既に通った場所なのかを記録しておく配列
int s_x, s_y, g_x, g_y;
bool dfs(int x, int y) {
    used[x][y] = true;
    if (x == g_x && y == g_y) { // ゴールに着いた時
        return true;
    }
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    REP(i, 4) {
        int nx = x + dx[i]; // 次の探索場所の行番号
        int ny = y + dy[i]; // 次の探索場所の列番号
        if (0 <= nx && nx < H && 0 <= ny && ny < W && maze[nx][ny] != '#' && !used[nx][ny]) {
            if (dfs(nx, ny)) { // ゴールに着く経路があれば終了
                return true;
            }
        }
    }
    // ゴールに到達できなければfalse
    return false;
}
int main() {
    memset(used, 0, sizeof(used));
    cin >> H >> W;
    REP(i, H) {
        REP(j, W) {
            cin >> maze[i][j];
            if (maze[i][j] == 's') {
                s_x = i;
                s_y = j;
            } else if (maze[i][j] == 'g') {
                g_x = i;
                g_y = j;
            };
        }
    }
    if (dfs(s_x, s_y)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    };
    return 0;
}