Java 13ms Iterative DFS solution with Explanation


  • 5
    S

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

    Mapping of element value in visited array to colors in CLRS DFS algorithm:
    0 -> White, -1 -> Gray, 1 -> Black

    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.

    For the end of the corresponding dfs search rooted at prere: -1 corresponding to prere as a normal node; 1 corresponding to prere as an end node of a cross edge.

    My Java implementation of the iterative DFS algorithm based on its recursive counterpart in CLRS (13ms):

    public class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            int[] visited = new int[numCourses];
            List<List<Integer>> graph = new ArrayList<>();
            ArrayDeque<Integer> stack = new ArrayDeque<>();
            ArrayDeque<Integer> auxStack = new ArrayDeque<>();
            int[] order = new int[numCourses];
            
            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);
            }
            
            for (int i = 0; i < numCourses; i++) {
                if (visited[i] == 0) {
                    stack.push(i);
                    while (!stack.isEmpty()) {
                        Integer prere = stack.peek();
                        if(visited[prere] == 0) {
                            // start of dfs search rooted at prere
                            visited[prere] = -1;
                        }
                        else if (visited[prere] == -1){
                            // end of dfs search rooted at prere; prere is a normal node
                            stack.pop();
                            visited[prere] = 1;
                            auxStack.push(prere);
                            continue;
                        } 
                        else if (visited[prere] == 1) {
                           // since prere is an end node of a cross edge; the dfs search rooted at prere
                           // has been finished as part of another dfs search rooted at another node
                           // we have no need to explore its neighbors again
                            stack.pop();
                            continue;
                        }
                        for (Integer course: graph.get(prere)) {
                            if (visited[course] == 0) {
                                stack.push(course);
                            }
                            else if (visited[course] == -1) {
                                return new int[0];
                            }
                        }
                    }
                    
                }
            }
            for (int i = 0; i<numCourses; i++) {
                order[i] = auxStack.pop();
            }
            return order;
        }
    }
    

    Just for comparison, here is my Java implementation of the recursive DFS algorithm in CLRS (8ms):

    public class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            int[] visited = new int[numCourses];
            ArrayDeque<Integer> stack = new ArrayDeque<Integer>();
            List<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
            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, stack, i)) return new int[0];
            }
            int[] order = new int[numCourses];
            for (int i = 0; i < numCourses; i++) 
                order[i] = stack.pop();
            return order;
        }
        
        private boolean dfsDetectCycle(List<ArrayList<Integer>> graph, int[] visited,
                                                  ArrayDeque<Integer> stack, int prere) {
            visited[prere] = -1; //Gray
            for (int course: graph.get(prere)) {
                if (visited[course] == -1) return true;
                else if (visited[course] == 0 && dfsDetectCycle(graph, visited, stack, course)) return true;
            }
            visited[prere] = 1; //Black
            stack.push(prere);
            return false;
        }
    }
    

    My Java implementation of the BFS solution with indegree (11ms):

    public class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            int[] indegree = new int[numCourses];
            List<List<Integer>> graph = new ArrayList<>();
            Queue<Integer> queue = new ArrayDeque<>();
            int count = 0;
            int[] order = new int[numCourses];
            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();
                order[count++] = prere;
                for (Integer course: graph.get(prere)) {
                    if (--indegree[course] == 0) 
                        queue.offer(course);
                }
            }
            if(count == numCourses) {
                return order;
            }
            else {
                return new int[0];
            }
        }
    }
    

Log in to reply
 

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