[white-gray-black in DFS] LeetCo

DFS - Depth First Search

DFS是我们常用的关于graph的算法。它的策略是对于已发现的node，尽可能深的探索它的children。

今天讲讲"white-gray-black" DFS algorithm。其实还是DFS，但这里引入一个用color来记录search的过程。

假设在search前，graph里面所有node都是white，我们从某个node开始做DFS，在DFS过程中，新发现的node改为gray。如果一个node的所有children都被search过（也就是回溯的过程中），这个node改为black。

LeetCode题目

LeetCode 802 - Find Eventual Safe States就可以用这种方法。

想法一
我们visit node，entry的时候mark为gray, exit的时候mark为black。如果我们在DFS过程中看到了gray，它肯定是一个cycle。

下面是官方给的其中一种答案：

class Solution {
    public List<Integer> eventualSafeNodes(int[][] graph) {
        int N = graph.length;
        int[] color = new int[N];
        List<Integer> ans = new ArrayList();

        for (int i = 0; i < N; ++i)
            if (dfs(i, color, graph))
                ans.add(i);
        return ans;
    }

    // colors: WHITE 0, GRAY 1, BLACK 2;
    public boolean dfs(int node, int[] color, int[][] graph) {
        if (color[node] > 0) // color > 1，表示被访问过
            return color[node] == 2; // color == 2，表示它的children已经search完了

        // 走到这里，说明这是一个新的node
        color[node] = 1; // mark为search过
        for (int nei: graph[node]) {
            if (color[node] == 2)
                continue; // children都被search过就不用再search了
            if (color[nei] == 1 || !dfs(nei, color, graph))
                return false; 
        }

        color[node] = 2;
        return true;
    }
}

Complexity Analysis

• Time Complexity: O(N + E), where N is the number of nodes in the given graph, and E is the total number of edges.
• Space Complexity: O(N) in additional space complexity.

想法二
我们可以反向记录graph连接方式：我们记录每个node incoming的node，就是谁指向了它。然后我们找孤立的node，就是stop的node，再反向推，找谁指向stop node（假设是node A, B），把node A, B的outgoing数目都减一，如果减完之后A和B还有outgoing，那就是形成cycle的outgoing（因为不形成cycle的话，必须指向stop node）。

code实现很简单，大家可以自己试试。