Explained Java 12ms Iterative DFS solution based on DFS algorithm in CLRS


  • 7
    S

    Just FYI, here is my solution for the other problem: Course Schedule II.

    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            int[] visited = new int[numCourses];
            List<List<Integer>> graph = new ArrayList<>();
            ArrayDeque<Integer> stack = new ArrayDeque<>();
            for (int i = 0; i < numCourses; i++) {
                graph.add(new ArrayList<Integer>());
            }
            for (int i = 0; i < prerequisites.length; i++) {
                int course = prerequisites[i][0], prere = prerequisites[i][1];
                graph.get(prere).add(course);
            }
            //mapping of element value in visited array to colors in CLRS DFS algorithm: 
            //0 -> White, -1 -> Gray, 1 -> Black
            for (int i = 0; i < numCourses; i++) {
                if (visited[i] == 0) {
                    stack.push(i);
                    while (!stack.isEmpty()) {
                        // We need to peek a node in stack for the first time, and pop it 
                        // for the second time we meet it. In other words, we need to 
                        // keep a node in stack until the dfs search rooted at it
                        // has been finished, which is equivalent to the end of a recursive call
                        Integer prere = stack.peek();
                        if(visited[prere] == 0) {
                            visited[prere] = -1;
                        }
                        else if (visited[prere] == -1 || visited[prere] == 1) {
                            // for the end of the corresponding recursive dfs call rooted at prere
                            //-1 corresponding to prere as a normal node
                            //1 corresponding to prere as an end node of a cross edge 
                            stack.pop();
                            visited[prere] = 1;
                            continue;
                        }
                        for (Integer course: graph.get(prere)) {
                            if (visited[course] == 0) {
                                stack.push(course);
                            }
                            else if (visited[course] == -1) {
                                return false;
                            }
                        }
                    }
                    
                }
            }
            return true;
        }
    }
    

    Just for comparison, my solution implementing recursive DFS (7ms):

    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            int[] visited = new int[numCourses];
            List<List<Integer>> graph = new ArrayList<>();
            for (int i = 0; i < numCourses; i++) {
                graph.add(new ArrayList<Integer>());
            }
            for (int i = 0; i < prerequisites.length; i++) {
                graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
            }
            for (int i = 0; i < numCourses; i++) {
                if (visited[i] == 0 && dfsDetectCycle(graph, visited, i)) return false;// 0: White
            }
            return true;
        }
        
        private boolean dfsDetectCycle(List<List<Integer>> graph, int[] visited, int prere) {
            visited[prere] = -1; //-1: Gray
            for (Integer course: graph.get(prere)) {
                if (visited[course] == -1) return true;
                else if (visited[course] == 0 && dfsDetectCycle(graph, visited, course)) return true;
            }
            visited[prere] = 1; //1: Black
            return false;
        }
    }
    

    My implementation of BFS solution using indegree:

    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            int[] indegree = new int[numCourses];
            List<List<Integer>> graph = new ArrayList<>();
            int count = 0;
            Queue<Integer> queue = new ArrayDeque<>();
            for (int i = 0; i < numCourses; i++) {
                graph.add(new ArrayList<Integer>());
            }
            for (int i = 0; i < prerequisites.length; i++) {
                int course = prerequisites[i][0], prere = prerequisites[i][1];
                indegree[course]++;
                graph.get(prere).add(course);
            }
            for (int i = 0; i < numCourses; i++) {
                if (indegree[i] == 0) {
                    queue.offer(i);
                }
            }
            
            while (!queue.isEmpty()) {
                Integer prere = queue.poll();
                count++;
                for (Integer course: graph.get(prere)) {
                    if (--indegree[course] == 0) {
                        queue.offer(course);
                    }
                }
            }
            return count == numCourses;
            
        }
    }
    

Log in to reply
 

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