再帰関数による深さ優先探索をALDS1_11_Bを例題にして学ぶ

再帰関数による深さ優先探索をALDS1_11_Bを例題にして、学びます。
深さ優先探索の考え方については、こちらにまとめています。

例題

深さ優先探索（Depth First Search: DFS）は、可能な限り隣接する頂点を訪問する、という戦略に基づくグラフの探索アルゴリズムです。
未探索の接続辺が残されている頂点の中で最後に発見した頂点 v の接続辺を再帰的に探索します。

v の辺をすべて探索し終えると、vを発見したときに通ってきた辺を後戻りして探索を続行します。
探索は元の始点から到達可能なすべての頂点を発見するまで続き、 未発見の頂点が残っていれば、その中の番号が一番小さい１つを新たな始点として探索を続けます。

深さ優先探索では、各頂点に以下のタイムスタンプを押します：

• タイムスタンプ d[v]: vを最初に発見した発見時刻を記録します。
• タイムスタンプ f[v]: vの隣接リストを調べ終えた完了時刻を記録します。

以下の仕様に基づき、与えられた有向グラフ G=(V,E)
に対する深さ優先探索の動作を示すプログラムを作成してください：

Gは隣接リスト表現の形式で与えられます。
各頂点には 1 から nまでの番号がふられています。 各隣接リストの頂点は番号が小さい順に並べられています。 プログラムは各頂点の発見時刻と完了時刻を報告します。 深さ優先探索の過程において、訪問する頂点の候補が複数ある場合は頂点番号が小さいものから選択します。 最初に訪問する頂点の開始時刻を 1 とします。

入力

最初の行に G の頂点数 n が与えられます。続く n 行で各頂点 u の隣接リストが以下の形式で与えられます：

u k v1 v2 ... vk

u は頂点の番号、k は u の出次数、v1v2...vk 　は u に隣接する頂点の番号を示します。

出力

各頂点について id、 d、 fを空白区切りで１行に出力してください。
id は頂点の番号、d はその頂点の発見時刻、f はその頂点の完了時刻です。頂点の番号順で出力してください。

制限

1≤n≤100

入力例

4
1 1 2
2 1 4
3 0
4 1 3

出力例

1 1 8
2 2 7
3 4 5
4 3 6

解法

隣接リストで与えられる入力に対して、隣接行列を作り、それをGraphとすると Graphに対し、深さ優先探索を再帰関数で行うプログラムは以下のようになります。

void visit(int i){
    // 1
    visited[i] = true;
    // 2
    for(int j = 0;j < max;++j){
        if(Graph[i][j] == 1 && !visited[j]){
            visit(j);
        }
    }
}

1.頂点を探索したことを示すフラグvisitedを用意し、
探索した段階で、フラグを立てます。

2.与えられた頂点から隣接行列を調べていき、隣接する頂点を調べます。
すでに探索している頂点の場合処理を飛ばすことで、ループになることを防いでいます。

タイムスタンプへの対応方法

問題では、頂点の探索開始時刻と探索終了時刻を記録する必要があります。

探索開始時点は、探索する前である、関数visitの2の処理の前におけばよく、
探索終了時点は、2の派生する点の探索が終わった時点で換算することになります。

c++での解法例

それでは、以上を踏まえたc++での解法例を書きます。

#include <iostream>

using namespace std;

#define N 100

int Graph[N][N];
// 頂点を発見した時刻
int d[N];
// 頂点の探索を終えた時刻
int f[N];
// かかった時間
int dTime = 0;
// 頂点を発見したかのフラグ
bool visited[N];

void visit(int i,int max){
    
    visited[i] = true;
    d[i] = ++dTime;
    for(int j = 0;j < max;++j){
        if(Graph[i][j] == 1 && !visited[j]){
            visit(j,max);
        }
    }
    // すべての頂点の探索が終了した
    f[i] = ++dTime;
}

int main(){
    int n,u,k,v;

    cin >> n;
    for(int i = 0;i < n;++i){
        cin >> u >> k;
        // 頂点を移動する
        u--;
        // 頂点の数だけ回す
        for(int j = 0;j < k;++j){
            cin >> v;
            --v;    // ずらす
            Graph[u][v] = 1;
        }
    }
    for(int i = 0;i < n;++i){
        if(!visited[i]){
            visit(i, n);
        }
    }
    
    for(int i = 0;i < n;++i){
        cout << i + 1 << " " << d[i] << " " << f[i] << endl;
    }
    
    return 0;
}

計算量を考える

隣接行列を使い2重ループですべてのパターンを調べているので、
$O(N^2)$の計算量がかかることになります。