スタックによる深さ優先探索をALDS1_11_Bを使って学ぶ

スタックを使用して、深さ優先探索を行う方法をAIDU_ONLINE_JUDGEの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

スタックを利用した深さ優先探索

スタックにまだ探索中の頂点を一時的に保存しておくことにより、
深さ優先探索を行います。

手順は以下のようになります。

1.一番最初に訪問する頂点をスタックに入れる

2.スタックに頂点が積まれている限り、以下の処理を繰り返します。

• スタックの先頭に積まれている頂点uを訪問する
• 現在訪問中の頂点uから次の頂点vへ探索を移行するときに、
  頂点vをスタックに積みます。
  現在訪問中の頂点uに未訪問の隣接する頂点なければuをスタックから解放します。

スタックの処理例

以下のグラフを例にスタックによる、深さ優先探索を行って見たいと思います。

1.最初に訪問する頂点を0としてスタックに積みます

2.スタックの先頭の0を訪問します。
0に隣接し、かつ未訪問で、数の小さい方の頂点1をスタックに積みます。

3.スタックの先頭1を訪問します。
1に隣接しており、未訪問の3をスタックに積みます。

4.スタックの先頭3を訪問します。
3に隣接し、未訪問の2をスタックに積みます

5.スタックの先頭2を訪問します。
頂点2に隣接して未訪問な頂点は存在しないので、2をスタックから削除します。

6.スタック先頭の3を再び訪問します。 頂点3に隣接して、未訪問の頂点6をスタックに積みます。

7.スタックの先頭6を訪問します。
頂点6に隣接して、未訪問の頂点5をスタックに積みます。

8.スタックの先頭5を訪問します。
頂点5に隣接して、未訪問の頂点4をスタックに積みます。

8.スタックの先頭4を訪問します。
頂点4に隣接して、未訪問の頂点の頂点はないので、4をスタックから削除します。

9.スタックの先頭5訪問します。
頂点5に隣接して、未訪問の頂点の頂点はないので、5をスタックから削除します。

10.スタックの先頭6訪問します。
頂点6に隣接して、未訪問の頂点の頂点はないので、6をスタックから削除します。

11.スタックの先頭3訪問します。
頂点3に隣接して、未訪問の頂点の頂点はないので、3をスタックから削除します。

12.スタックの先頭1訪問します。
頂点1に隣接して、未訪問の頂点の頂点はないので、1をスタックから削除します。

13.スタックの先頭0訪問します。
頂点0に隣接して、未訪問の頂点の頂点はないので、0をスタックから削除します。

14.スタックが空となり、すべての頂点の訪問が完了しました。

スタックによる深さ優先探索に必要な変数一覧

スタックによる深さ優先探索に必要な変数は以下のようになります。

変数名例	役割
color[N]	未訪問・訪問中・訪問済みの状態を表すための変数
M[n][n]	グラフの隣接行列を表すための変数、頂点が隣接している場合は1(true)など
Stack s	訪問中の頂点を退避しておくためのスタック

スタックによる深さ優先探索の疑似アルゴリズム

以上の処理を疑似アルゴリズムにまとめてみます。

dfs(u)
 S.push(u) // 始点をスタックに追加
 color[u] = 訪問中
 d[u] = ++time; // 訪問時間を代入する
 
 while(sが空でない)
  u = S.top()
  v = next(u) // uに隣接している頂点を昇順になるように取得する
  if v != NIL
   if color[v] == 未訪問
    color[v] = 訪問中
    d[v] = ++time; // 訪問時間を記録
    S.push(v)
   // 隣接する頂点がない場合   
  else
   S.pop()
   color[v] = 訪問済み
   f[u] = ++time; // 探索が終わった時間を記録

stackを使い隣接行列を用いた計算量

各々の頂点について、隣接しているすべての頂点を調べるので、
計算量は$O[n^2]$の計算量になります。

c++による、stackを利用した例題の解法

最後に隣接行列とstackを利用した問題のc++での解法を載せます。

#include<iostream>
#include<stack>
using namespace std;

#define N 100
// 未訪問
#define WHITE 0
// 訪問中
#define GRAY 1
// 訪問済み
#define BLACK 2

int n,M[N][N];
int color[N];
// 訪問時間
int d[N];
// 探索終了時間
int f[N];
// 時間
int t = 0;
// 探索済みの頂点を一から探索しないように、nt[u]にすでに探索済みの番号を入れ、
// 次回は探索した移行の頂点から探索されるようにする
int nt[N];

/**
    uに隣接するvを番号順に取得する
*/
int next(int u){
    // 探索済み移行の頂点から探索を始める
    for(int v = nt[u];v < n;++v){
        nt[u] = v + 1;
        if(M[u][v]){
            return v;
        }
    }
    return -1;
}

/**
    スタックを用いた深さ優先探索
*/
void dfs(int u){
    for(int i = 0;i < n;++i){
        nt[i] = 0;
    }
    
    stack S;
    S.push(u);
    color[u] = GRAY;    // 訪問中
    d[u] = ++t;      // 訪問時間
    
    while(!S.empty()){
        int topU = S.top();
        // 隣接する頂点
        int v = next(topU);
        // 隣接する頂点が見つかった場合
        if(v != -1){
            // 未探索のケース
            if(color[v] == WHITE){
                color[v] = GRAY;
                // 訪問時間
                d[v] = ++t;
                S.push(v);
            }
        }else{
            // 未訪問の頂点が見つからなかった
            S.pop();
            // 探索終了
            color[topU] = BLACK;
            // 探索終了時間
            f[topU] = ++t;
        }
    }
}

int main(){
    int u,k,v;
    cin >> n;
    
    // 初期化
    for(int i = 0;i < n;++i){
        color[i] = WHITE;
        for(int j = 0;j < n;++j){
            M[i][j] = 0;
        }
    }
    
    for(int i = 0;i < n;++i){
        cin >> u >> k;
        // 頂点を移動する
        u--;
        // 頂点の数だけ回す
        for(int j = 0;j < k;++j){
            cin >> v;
            --v;    // ずらす
            M[u][v] = 1;
        }
    }
    for(int i = 0;i < n;++i){
        if(color[i] == WHITE){
            dfs(i);
        }
    }
    
    for(int i = 0;i < n;++i){
        cout << i + 1 << " " << d[i] << " " << f[i] << endl;
    }
    
    return 0;
}