深さ優先探索

深さ優先探索(Depth First Search)とは

　グラフを探索するアルゴリズム。可能な限りある頂点に隣接する頂点を訪問するという戦略に基づいています。 未探索の接続辺が残されている頂点の中で最後に発見した頂点 v の接続辺を再帰的に探索します。 v の辺のすべて探索し終えると、 v を発見したときに通ってきた辺を後戻りして探索を続行します。

　探索はもとの始点から到達可能なすべての頂点を発見するまで続き、未発見の頂点が残っていれば、その中の番号が一番小さい 1 つを新たな始点として探索を続けます。

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

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

深さ優先探索の理解を深めるために以下のような有向グラフを考えます。

図 1 f:id:d_tutuz:20180201080912p:plain

上記の有向グラフを行 i (1\leq i\leq6) 、列 j (1\leq j\leq6) の 2 次元行列で表すと以下のようになります。 a_{ij} について a_{ij} = 1 ならば、 i から j へ辺が存在することを意味します。

$$ \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} $$

例えば頂点 1 からは 2 と 4 へ辺が存在するため、行列上では a_{12},a_{14} が 1 になっています。 この有向グラフを深さ優先で探索したときに付与するタイムスタンプは以下のようになります。

図 2 f:id:d_tutuz:20180201080913p:plain

深さ優先探索の実装としては、

  • スタックを用いる方法
  • 再帰を用いる方法

の 2 種類があるのですが、今回は再帰による実装を試みます。

標準入力としては、以下のように最初の 1 行目に有向グラフの頂点数 N が与えられ、その次の行からに N × N 行列が与えられるものとします。

6
0 1 0 1 0 0
0 0 0 0 1 0
0 0 0 0 1 1
0 0 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 1

出力すべきは各頂点 v ごとの d[v] と f[v] です。 図 2 のような結果は以下のよう v\,\,d[v]\,\,f[v] と表すこととします。

1 1 8
2 2 7
3 9 12
4 4 5
5 3 6
6 10 11

実装

Javaによる実装は以下のようになります。

import java.util.Scanner;

public class DepthFirstSearchSample {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] matrix = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }
        int[] d = new int[n + 1];
        int[] f = new int[n + 1];
        int count = 0;

        // 1から順番に頂点を探索
        for (int i = 1; i <= n; i++) {
            count = dfs(matrix, d, f, i, count);
        }

        for (int i = 1; i <= n; i++) {
            System.out.println(i + " " + d[i] + " " + f[i]);
        }
        sc.close();
    }

    static int dfs(int[][] matrix, int[] d, int[] f, int now, int count) {
        // すでに初回訪問済の場合はとばす
        if (d[now] != 0) {
            return count;
        }
        // 初回訪問時の記録
        d[now] = ++count;
        for (int i = 1; i < matrix.length; i++) {
            // 遷移先頂点が存在する場合は遷移して、再帰的に探索
            if (matrix[now][i] == 1) {
                count = dfs(matrix, d, f, i, count);
            }
        }
        // 隣接する未訪問頂点が存在しなかった場合は完了の記録
        f[now] = ++count;
        return count;
    }

}

参考