プログラミング原人の進化ログ

プログラミング原人の進化論

オレ プログラミング ベンキョウ スル。マナンダ コト カク。

深さ優先探索を実装してみた

深さ優先探索を勉強したのでメモしておきます。

深さ優先探索

深さ優先探索(Depth First Search, DFS)はグラフを用いた代表的な探索アルゴリズムです。大まかにスタックを使ったものと再帰を利用したものという2つの実装方法があります。基本的なアイディアは、始点からたどっていき、それ以上進めない節点までたどり着いたら引き返し、未探索部分を同様に探索していくというものです。下の図のような手順で節点を訪問します。

f:id:programgenjin:20190313111341p:plain

経路の探索などに使われることが多いようです。

アルゴリズム

スタックを用いた場合のアルゴリズムは次のようになります。

  1. 始点となる頂点をスタックに入れる。
  2. スタックが空になるまで以下を繰り返す:
    • スタックの頂点を取り出し、処理を行う(訪問する)。
    • 訪問した頂点のneighbors(隣接する頂点)のうち、未訪問のものをスタックに積む。

問題を解いてみる

言語はC++です。

深さ優先探索 | アルゴリズムとデータ構造 | Aizu Online Judge

訪問順だけでなく、隣接する全ての頂点を調べ終えた時刻を記録しなければならないので、少々面倒ですが...。 ここでは訪問状態を色で管理します。

  • white:未訪問
  • gray :訪問済みだが、隣接する頂点を調べ終わっていない
  • black:訪問済み、隣接する頂点も全て訪問した

スタックと再帰関数、2つを利用した場合の解答を示します。

スタックを用いた場合: grayの頂点をスタックに入れておきます。

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

#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int M[N+1][N+1];  // 隣接行列

// 隣接している順番に頂点を取得
int next(int vertex, int neighbors[], int n) {
  for (int i = neighbors[vertex] + 1; i <=n; i++) {
    if (M[vertex][i] == 1) {
      neighbors[vertex] = i;
      return i;
    }
  }
  return 0;  // 隣接する頂点を全て探索した場合
}

void dfs(int n, int d[], int f[]) {
  int i, time, vertex, neighbor, neighbors[N+1];
  int color[N+1];
  stack<int> s;  // GRAYの頂点を入れておく

  // 初期状態
  for (i = 1; i <= n; i++) {
    color[i] = WHITE;
    neighbors[i] = 0;
  }
  vertex = 1;  // 頂点
  time = 0;    // 時刻

  // dfs
  for (i = 1; i <= n; i++) {
    if (color[i] == WHITE) {
      vertex = i;  // 頂点
      s.push(vertex);
      color[vertex] = GRAY;
      d[vertex] = ++time;
      
      while (!s.empty()) {
        vertex = s.top();
        neighbor = next(vertex, neighbors, n);    
        if (neighbor) {  // 隣接する頂点に未探索あり
          if (color[neighbor] == WHITE) {  
            color[neighbor] = GRAY;  // neighborを訪問
            d[neighbor] = ++time;
            s.push(neighbor);
          }
        } else {  // 隣接する頂点を全て探索した
          color[vertex] = BLACK;
          f[vertex] = ++time;
          s.pop();  // stackから削除
        }
      }
    }
  }
}

int main() {
  int i, j, n, u, k, v, d[N+1], f[N+1];

  cin >> n;
  // 与えられた隣接リスト表現を隣接行列表現に直す  
  for (i = 1; i <= n; i++){
    for (j = 1; j <= n; j++) {
      M[i][j] = 0;
    }
  }
  for (i = 0; i < n; i++) {
    cin >> u >> k;
    for (j = 0; j < k; j++) {
      cin >> v;
      M[u][v] = 1;
    }
  }

  dfs(n, d, f);

  // 出力
  for (i = 1; i <= n; i++) cout << i << " " << d[i] << " " << f[i] << endl;
  
  return 0;
}

再帰関数を使った場合:

#include<iostream>
using namespace std;

#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2

int time_stamp;
int M[N+1][N+1];

void dfs(int n, int vertex, int d[], int f[], int color[]) {  
  color[vertex] = GRAY;
  d[vertex] = ++time_stamp;
  for (int i = 1; i <= n; i++) {    
    if (M[vertex][i] && color[i] == WHITE) {
      dfs(n, i, d, f, color);
    }
  }
  color[vertex] = BLACK;
  f[vertex] = ++time_stamp;
}

void search(int n, int d[], int f[], int color[]) {
  // 初期状態
  for (int i = 1; i <= n; i++) color[i] = WHITE;
  time_stamp = 0;
  // dfs
  for (int i = 1; i <= n; i++) {
    if (color[i] == WHITE) {
      dfs(n, i, d, f, color);
    }
  }
}

int main() {
  int i, j, n, u, k, v, d[N+1], f[N+1], color[N+1];
  
  cin >> n;
  // 隣接行列を取得
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      M[i][j] = 0;
    }
  }
  for (i = 0; i < n; i++) {
    cin >> u >> k;
    for (j = 0; j < k; j++) {
      cin >> v;
      M[u][v] = 1;
    }
  }

  search(n, d, f, color);

  for (i = 1; i <= n; i++) cout << i << " " << d[i] << " " << f[i] << endl;    

  return 0;
}

再帰関数を用いるとだいぶ簡潔に書けました。

参考

渡部有隆. プログラミングコンテスト攻略のためのアルゴリズムとデータ構造. Ozy, 秋葉拓哉協力. 株式会社マイナビ. 2015.