Detailed Comment on DFS solution for Course Schedule I & II


  • 3

    Re: Java DFS and BFS solution

    For the DFS part, I can understand now. Thanks for sharing! For more details, please refer to classic CLRS.

    The 0, 1, 2 in visited array corresponds to White, Gray, Black in CLRS. As CLRS says, The key idea is that when we first explore an edge, the color of vertex tells us something about the edge:

    1. WHITE (vis[nb] == 0) indicates a tree edge,
    2. GRAY (vis[nb] == 1) indicates a back edge, and
    3. BLACK (vis[nb] == 2) indicates a forward or cross edge.
        public boolean canFinish(int n, int[][] prereq) {
            List<Integer>[] adj = new List[n];
            for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
            for (int[] e : prereq) adj[e[1]].add(e[0]);
            
            int[] vis = new int[n];     // reuse so that each node visited once
            for (int i = 0; i < n; i++) // must check every node. eg.[1,0],[0,1]
                if (dfs(adj, i, vis)) return false;
            return true;
        }
        
        // Check if back edge (directed cycle) exists. If not => DAG => able to topo sort
        private boolean dfs(List<Integer>[] adj, int v, int[] vis) {
            vis[v] = 1;
            for (int nb : adj[v]) {
                if (vis[nb] == 1) return true; // visited and nb is v's ancestor => back edge
                if (vis[nb] == 0 && dfs(adj, nb, vis)) return true; // nb is not visited => tree edge
                // else vis[nb]==2, nb is visited but not ancestor => forward or cross edge
            }
            vis[v] = 2;
            return false;
        }
    

    The illustration below is an example. F for forward edge, C for cross edge, B for back edge.

    edges

    Using same idea, we can solve Course Schedule II in DFS manner as well. The key note is Topo-sort order is the reverse order of their finish time.

        public int[] findOrder(int n, int[][] prereq) {
            List<Integer>[] adj = new List[n];
            for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
            for (int[] e : prereq) adj[e[1]].add(e[0]);
            
            LinkedList<Integer> ret = new LinkedList<>();
            int[] vis = new int[n];
            for (int i = 0; i < n; i++)
                if (vis[i] == 0 && dfs(ret, adj, i, vis)) return new int[0];
            return ret.stream().mapToInt(i -> i).toArray();
        }
        
        private boolean dfs(LinkedList<Integer> ret, List<Integer>[] adj, int v, int[] vis) {
            vis[v] = 1;
            for (int nb : adj[v]) {
                if (vis[nb] == 1) return true;
                if (vis[nb] == 0 && dfs(ret, adj, nb, vis)) return true;
            }
            vis[v] = 2;
            ret.addFirst(v); // Topo-sort order is the reverse order of their finish time
            return false;
        }
    

  • 0

    Nice, but it seems I can't initialize the adjacency list as you did List<Integer>[] adj = new List[n]; in eclipse. How come?
    Update: It's just a warning, but still don't understand why it can be like this: Type safety: The expression of type List[] needs unchecked conversion to conform to List<Integer>[]


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.