DFSのお勉強

DFSの勉強

「いい加減DFSくらいソラで書けるようになれ」という天啓を受けたので勉強します。

DFSとは?

Depth First Searchの頭文字を取ってDFSと呼びます。Depth-First = 深さ第一、 Search = 探索という訳から深さ優先探索と呼ばれます。

一般的にDFSは樹形図を全探索する操作として捉えることができます。
例えば1~4が書かれた4枚のカードを$k \ (1 \le k \le 4)$枚取ることにしたとき、順番を考えずに取る場合の数は $\sum_{k=1}^4{\left({}_4C_k\right)}$ により求めることができます。

また、この15通りを樹形図で列挙すると以下のようになります。

このようないくつかの樹形図を探索する以外にも、もっと直感的な木(グラフ)の探索などを行うことができます。
これは後に述べます。

補集合列挙

先程取り扱ったカードを選ぶ問題を考えてみます。
カードを選ぶ順番が場合の数に関係しないことを考えると、もはや4枚のうち$i(1 \le i \le 4)$番目のカードを選んだか選んでいないかのみで場合が分岐することがわかります。

したがって全体集合$U$をカードに書かれた数字に従って以下のように定義すると、このカードを1枚以上選ぶという問題は$U$に属する$\phi$を除くすべての補集合を列挙する問題に帰着できます。(以下の画像を参照してください。ここでは便宜上要素を選ばないことを要素の上にバーを表記することとしています。)

$$
U = {1, 2, 3, 4}
$$

そして、これは$k$の値によって場合分けしたときの樹形図よりもより直感的な樹形図であり、典型的な木であるということがわかります。(グラフ理論的にはこれを完全二分木と呼ぶのでしょうか?よくわかっていません...)

この補集合を探索する方法としてBit全探索やDFSがすぐに思いつくと思います。
今回はDFSの話なのでBit全探索による探索は解説しません。

まず、方針はこうです。

• DFS関数を定義し、初期値に空集合をVector配列として与える。
• 次に選ぶべきカードの番号を持ち、そのカードを選ぶか選ばないかをシミュレートする(これはVector配列にカードを追加するかしないかでシミュレートできる。)
• 選択すべきカードを見終えたらできた配列を出力

こうすることですべての補集合を列挙できます。

DFSは特殊で、本来はStackを用いて構築しますが、再帰関数を用いて構築することも可能です。(実際は再帰関数の場合も関数呼び出しがスタック領域に積まれるだけなので同じですが...)

//numbers of the cards; now deck; next card
void dfs(int n, vector<int> now, int select){
    vector<int> next = now;
    next.push_back(select);
    if (select <= n) {
        dfs(n, now, select+1); //Not append the card
        dfs(n, next, select+1); //Append the card
    }
    else pvect(now); //Print out
}

//nuber of the cards
void stack_bfs(int n){
    //Selected i-th, now deck
    stack<pair<int, vector<int>>> st;

    st.push({0, {}}); //Initialize stack

    while(!st.empty()){
        auto [selected, now] = st.top(); //Pop next target
        st.pop();

        if (selected == n) pvect(now); //All choiced
        else{
            vector<int> next = now;
            next.push_back(selected+1);
            st.push({selected+1, next}); //Append i-th card
            st.push({selected+1, now}); //Not append
        }
    }
}

上に示す2つの関数は4枚について選択を完了した後、以下の表示関数にVector配列を投げます。

void pvect(vector<int> a){
    cout << '{';
    for (int i = 0; i < (int)a.size(); i++){
        if (i < (int)a.size()-1) cout << a[i] << " ";
        else cout << a[i];
    }
    cout << '}' << endl;
}

この2つの関数の実行結果はどちらも下のようになります。

{}
{4}
{3}
{3 4}
{2}
{2 4}
{2 3}
{2 3 4}
{1}
{1 4}
{1 3}
{1 3 4}
{1 2}
{1 2 4}
{1 2 3}
{1 2 3 4}

再帰関数で記載するほうがコードの記述量自体は少なくなりますが、選択肢の数によってはスタックオーバーフローを起こす危険性があります。また、関数呼び出しのオーバーヘッドが発生するので考慮すべき時間ではないですが多少時間がかかります。

重複順列

先程はカードがそれぞれ1枚のみしか存在しませんでしたが、4回の試行の中で同じカードを選択することができる場合があります。
これは以下のような問題に帰着されます。

目の前に4枚のカードがある。カードにはそれぞれ1から4までの数字が書かれており、あなたはこれから4回いずれかのカードを選ぶ。
直前に選択したカードを選んでも構わない。ただし、試行においてカードを選ばないことをしてはいけない。
カードを選び方をすべて列挙せよ。

これは先程の問題よりも単純です。

void dfs2(int n, vector<int> choice, vector<int> now){
    if ((int)now.size() == n){
        pvect(now);
    }
    else{
        for (int i = 0; i < (int)choice.size(); i++){
            vector<int> next = now;
            next.push_back(choice[i]);
            dfs2(n, choice, next);
        }
    }
}

この関数の出力結果は長いので省略します。(具体的には$4^4$通りがあります。)
要は、「入れる、入れない」を選択していた先ほどとは違い入れるカードの全探索を試行によって行っています。
あとは試行回数が規定の回数に到達したら先程と同様結果を出力しています。

例題

(回答は用意していないです...すいません...)

1

18枚の区別できるカードがある。$i(1 \le i \le 18)$番目のカードには整数$i$が書かれている。このカードから0枚以上18枚以下のカードを自由に選び、選んだカードの和が$n$となるのは何通りか。ただし、カードを選ぶ順序が違うだけの場合は区別しない。

• $0 \le n \le 171$

2

16枚の区別できるカードがある。$i(1 \le i \le 16)$番目のカードには整数$i$が書かれている。このカードから4枚のカードを自由に選び並び替えた後、カードに書かれた整数を左から順に足すか掛けるかして行ったとき、値が$n$となるのは何通りか。

注意:問題文に従い、通常の演算子の計算順序は無視される。すなわち、$1+2\times3$は本来$7$であるが、この問題では$9$となる。

• $10 \le n \le 43680$

グラフの深さ優先探索

グラフの持ち方は一般に二種類あります。それぞれ

• 隣接リスト表現(adjacency-list representation)
• 隣接行列表現(adjacency-matrix representation)

と呼ばれており、ここではよりメジャーな隣接リスト表現を用います。
隣接リスト表現は$N$個の頂点のうち$v$番目の頂点と$v'$番目の頂点を結ぶパスが存在するときに$v$番目の頂点に$v'$を記録しておくことでパスが存在することを表す方法です。

一般に二次元配列によって表現され、C++では

vector<vector<int>> g(n);

のように宣言されることが多々あります。

主に以下のような問題として与えられます。

AtCoder Beginner Contest 204 - C: Tour
AtCoder国には1から$N$までの番号がついた$N$個の都市と、1から$M$までの番号がついた$M$本の道路があります。
道路$i$は街$A_i$から$B_i$に続いています。$B_i$から$A_i$に到達することはできません。
これから何処かの街からスタートし、0本以上の道路を通ってどこかの街で旅を終えます。
始点と終点は全てで何通りありますか?

制約:
$2\le N \le 2000$
$0 \le M \le min(2000, N(N-1))$
$A_i \neq B_i$

これは、到達可能性問題と呼ばれるものです。
ある頂点$A$からスタートして頂点$B$に到達できるかを判定する問題ですが、これはDFSやBFSなどの探索で解くことが可能です。

グラフの深さ優先探索で面倒な部分は今までの場合の数の全探索と違いループが存在する可能性があることです。

したがって、ループが存在するグラフでも無限ループにならない工夫をする必要があります。
グラフの深さ優先探索では主に過去に訪れたことのある頂点を記録しておくという手法を取ります。

上のグラフで頂点1からDFSを開始するとしたときに以下のような配列を宣言します。

vector<bool> explored(n, false);
explored[0] = true;

このとき、exploredがすでに到達した頂点を記録します。
頂点1はスタート地点なので初期化としてスタート地点のみすでに訪れたことにします。

例えば頂点1から街2, 7に道がつながっているとすると以下のような値がグラフの頂点1に記録されているはずです。

{2, 7}

この記録をranged based forなどで読んであげて、次の頂点をまだ訪れていなければ訪れて、そのことを記録します。

上のようなグラフで無向グラフである場合はどの頂点からスタートしてもすべての頂点を訪れることができますが、有向グラフや非連結グラフではどの頂点からスタートしても全てがtrueになるということがない場合があります。

void dfs(int now, vector<vector<int>> &g, vector<bool> &explored){
    explored[now] = true;

    for (auto x : g[now]){
        if (explored[x] == true) continue;
        dfs(x, g, explored);
    }
}

int main(){
    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n);

    for (int i = 0; i < m; i++){
        int ai, bi;
        cin >> ai >> bi;
        g[ai-1].push_back(bi-1);
    }

    vector<bool> explored(n, false);
    long long ans = 0;
    for (int i = 0; i < n; i++){
        explored.assign(n, false);
        dfs(i, g, explored);

        int nt = 0;
        for (auto x : explored) if (x == true) nt++;

        ans += nt;
    }

    cout << ans << endl;
}

ABC204-C: Tourでは$N, M$の制約がともに小さく、$O(N+M)$だけ時間がかかるとしても$O(2000+2000) = O(1)$となり、十分高速です。
今回の問題はすべての頂点について$O(N+M)$だけ探索に時間がかかり、その後に$N$要素の線形探索があるので全体的な計算量としては$O(N^2)$だけかかります。

しかし、制約の$N$は十分小さいので最悪ケースでも$10^6$程度の計算しか行われません。
これは、実行制限時間の2秒に十分な余裕をもって間に合います。

オイラーツアーもどき

本物のオイラーツアーというのはタイムスタンプなどを用いて任意の頂点を根とする部分技を得ることができたりします。
が、ここではそもそも行きがけ順とか帰りがけ順とか、タイムスタンプとかをまだ使っていないわけで。導入する気もないので、オイラーツアーに似た探索を行ってみることにします。

AtCoder Beginner Contest 213 - D: Takahashi Tour
$1$から$N$までの街と、$1$から$N-1$の番号がついた$N-1$個の道路があります。
道路$i$は街$A_i$と$B_i$を相互につなぎます。

次のようなルールで街1を出発した後、訪れる街を順に答えてください。
ただし、全ての街は道路を使って互いに行き来することができるとします。

• 今いる街と道路で直接繋がっている街のうち、まだ訪れたことのない街が存在するなら、その中で最も小さい街を訪れる。
• そのような街が存在しないとき
  • 今いる街が街1なら終了
  • そうでないなら元いた街に戻る

ぶっちゃけるとこの街のネットワークは木です。
すべての$N$頂点が連結であるグラフが$N-1$本のパスを持つとき、そのグラフは木になります。
すべての頂点を1列につなぐ(パスグラフにする)と考えてみると、必要な本数はちょうど$N-1$本になるのは自明だと思います。

そのパスグラフを適当なところで切って、適当なところにつなげ変えたとしても、そのグラフが木であることは変わりません。

したがってこの街が木であることがわかります。
そこで、この問題は以下のように言い換えることができます。

すべての頂点を頂点番号の辞書順に一筆書きをして、訪れた順に頂点番号を出力せよ

これは以下のように実装できます。

void dfs(int now, vector<vector<int>> &g, vector<bool> &explored, vector<int> &stamp){
    stamp.push_back(now+1);
    explored[now] = true;
 
    for (auto x : g[now]){
        if (explored[x] == true) continue;
        dfs(x, g, explored, stamp);
        stamp.push_back(now+1);
    }
}
 
int main(){
    int n;
    cin >> n;
 
    vector<vector<int>> g(n);
 
    for (int i = 0; i < n-1; i++){
        int ai, bi;
        cin >> ai >> bi;
        g[ai-1].push_back(bi-1);
        g[bi-1].push_back(ai-1);
    }
 
    for (int i = 0; i < n; i++){
        sort(g[i].begin(), g[i].end());
    }
 
    vector<int> ans;
    vector<bool> explored(n, false);
    dfs(0, g, explored, ans);
 
    for (int i = 0; i < (int)ans.size(); i++){
        if (i != (int)ans.size()-1) cout << ans[i] << " ";
        else cout << ans[i] << endl;
    }
}

ある頂点の探索を始めるときに答えの配列の最後尾にpushし、その頂点から伸びる枝から帰ってきたときにもう一度その頂点番号をpushすることで、うまく行きと帰りの経路をメモすることができます。

頂点番号の辞書順であることからそれぞれの頂点について、つながる頂点の番号を最初にソートしておくとよいです(1敗)。

あとがき

AtCoderで言うところの茶DiffくらいまでのDFSを扱ってみました。
グラフのDFSにおけるコード２つは以下のリンクから提出コードを確認できます。
参考にする方はどうぞ。

ABC204-C AC提出
ABC213-D AC提出

正直DFSの動きがわかりにくいというのが最初の感想で、実際にこの記事を書く中でVerifyしたコードも存在します。
かなり勉強になったので別のアルゴリズムのお気持ちをまたやるかもしれません。
やるとしたらおそらくBFSかUnion-Findです。