Java DFS and BFS solution


  • 71
    S

    According to my code test, BFS is much faster than DFS. From my perspective DFS searches more branches. EX: 1->3->4 //1->5->3 the first branch we need search 3's children, in second we still need to do so.

    BFS:

    public class Solution {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            ArrayList[] graph = new ArrayList[numCourses];
            int[] degree = new int[numCourses];
            Queue queue = new LinkedList();
            int count=0;
            
            for(int i=0;i<numCourses;i++)
                graph[i] = new ArrayList();
                
            for(int i=0; i<prerequisites.length;i++){
                degree[prerequisites[i][1]]++;
                graph[prerequisites[i][0]].add(prerequisites[i][1]);
            }
            for(int i=0; i<degree.length;i++){
                if(degree[i] == 0){
                    queue.add(i);
                    count++;
                }
            }
            
            while(queue.size() != 0){
                int course = (int)queue.poll();
                for(int i=0; i<graph[course].size();i++){
                    int pointer = (int)graph[course].get(i);
                    degree[pointer]--;
                    if(degree[pointer] == 0){
                        queue.add(pointer);
                        count++;
                    }
                }
            }
            if(count == numCourses)
                return true;
            else    
                return false;
        }
    }
    

    DFS:

    public class Solution {
            public boolean canFinish(int numCourses, int[][] prerequisites) {
                ArrayList[] graph = new ArrayList[numCourses];
                for(int i=0;i<numCourses;i++)
                    graph[i] = new ArrayList();
                    
                boolean[] visited = new boolean[numCourses];
                for(int i=0; i<prerequisites.length;i++){
                    graph[prerequisites[i][1]].add(prerequisites[i][0]);
                }
    
                for(int i=0; i<numCourses; i++){
                    if(!dfs(graph,visited,i))
                        return false;
                }
                return true;
            }
    
            private boolean dfs(ArrayList[] graph, boolean[] visited, int course){
                if(visited[course])
                    return false;
                else
                    visited[course] = true;;
    
                for(int i=0; i<graph[course].size();i++){
                    if(!dfs(graph,visited,(int)graph[course].get(i)))
                        return false;
                }
                visited[course] = false;
                return true;
            }
        }

  • 0
    S

    Isn't that Topological Sort?


  • -2
    S

    the DFS solution is.


  • 0
    C
    This post is deleted!

  • 0
    C
    This post is deleted!

  • 11
    S

    Explanation for the DFS solution : the solution basically starts at every node in the graph which corresponds to a course and traverses all the courses (nodes) that can be taken subsequently. If we ever encounter the a course we have already visited , then we know there is a cycle. Note that in the solution , as the recursion unwinds all the visited status is set to false. Hence every time DFS is started in the can finish function , the visted boolean array is guaranteed to be all false. That is why this method works.


  • 10
    O

    i second this.
    I may be wrong, but the worst case runtime could be n^2 since you are not checking if any nodes are visited in the main for loop (the one in the canFinish function). This means you may be doing repeated searches. Imagine 1->2->3->4->5, when checking node (1) in the main loop, you'll be go through 2 - 5, but when you r checking node(2) in the main loop, you'll go through 3 - 5 again.


  • 0
    F

    What is the run time for them? (suppose m vertex and n edges)
    And what is the fast run time for this problem?


  • 0
    D

    hey could you explain why the visited has to reset to false at the end of dfs method?
    visited[course] = false;


  • 35
    J

    DFS with detailed comments:

    public class Solution {

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if(numCourses == 0 || prerequisites == null || prerequisites.length == 0) return true; //??
        
        // create the array lists to represent the courses
        List<List<Integer>> courses = new ArrayList<List<Integer>>(numCourses);
        for(int i=0; i<numCourses; i++) {
            courses.add(new ArrayList<Integer>());
        }
        
        // create the dependency graph
        for(int i=0; i<prerequisites.length; i++) {
            courses.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
    
        int[] visited = new int[numCourses]; 
        
        // dfs visit each course
        for(int i=0; i<numCourses; i++) {
               if (!dfs(i,courses, visited)) return false; 
        }
        
        return true;
    }
    
    private boolean dfs(int course, List<List<Integer>> courses, int[] visited) {
        
        visited[course] = 1; // mark it being visited
        
        List<Integer> eligibleCourses = courses.get(course); // get its children
        
        // dfs its children
        for(int i=0; i<eligibleCourses.size(); i++) {
            int eligibleCourse = eligibleCourses.get(i).intValue();
            
            if(visited[eligibleCourse] == 1) return false; // has been visited while visiting its children - cycle !!!!
            if(visited[eligibleCourse]  == 0) { // not visited
               if (!dfs(eligibleCourse,courses, visited)) return false; 
            }
    
        }
        
        visited[course] = 2; // mark it done visiting
        return true;
        
    }
    

    }


  • 0
    E

    I also dont understand this statement


  • 1
    P

    use raw type is not a good practice.


  • 1
    R

    The run time for this DFS solution is O(V + E^2). In the worst case described above by OBOBOB90 the algorithm needs to iterate over each course (which is O(V)), plus V^2 time to iterate over the course dependencies (O(E^2)).

    It is possible though to implement DFS algorithm with O(E) runtime (see this post).


  • 11
    H

    syftalent, prerequisites[i][1] is the prerequisite. You have this in BFS

           for(int i=0; i<prerequisites.length;i++){
            degree[prerequisites[i][1]]++;
            graph[prerequisites[i][0]].add(prerequisites[i][1]);
        }
    

    I think the [1] and [0] should be swapped, to this. It would then follow what I've seen in your DFS, and in other people's code, and follow my understanding of "indegree":

           degree[prerequisites[i][0]]++;
            graph[prerequisites[i][1]].add(prerequisites[i][0]);

  • 2
    Y

    The idea to use int array to represent visited status is brilliant. My java run time improves from 95 ms to 7 ms


  • 3
    M

    A little improvement about your DFS algorithm. I delete the edges when I searched them so that it will save a lot of time. Because we don't need to search them again if there are no cycles in the previous DFS process.

    DFS (14ms):

    public boolean canFinishDFS(int numCourses, int[][] prerequisites) {
        if (numCourses <= 1)
        	return true;
        ArrayList<HashSet<Integer>> edges = new ArrayList<HashSet<Integer>>(numCourses);
        boolean[] visited = new boolean[numCourses];
        
        for (int i = 0; i < numCourses; i++)
        	edges.add(new HashSet<Integer>());
        
        for (int[] pre: prerequisites){
        	edges.get(pre[0]).add(pre[1]);
        }
        
        for (int i = 0; i < numCourses; i++){
        	if (edges.get(i).size() != 0)
        		if (!dfs(edges, i, visited))
        			return false;
        }
        
        return true;
    }
    
    private boolean dfs(ArrayList<HashSet<Integer>> edges, int i, boolean[] visited){
    	if (visited[i] == true)
    		return false;
    	visited[i] = true;
    	while (edges.get(i).size() != 0){
    		int j = edges.get(i).iterator().next();
    		
    		if (!dfs(edges, j, visited))
    			return false;
    		
    		edges.get(i).remove(j);
    	}
    	//we only check the cycle in one DFS
    	visited[i] = false;
    	return true;
    } 

  • 0
    J

    I did similary way using DFS, it show time limit exceeded, any one know why?

    public boolean canFinish(int n, int[][] prerequisites) {
        List[] array=new List[n];
        for(int [] pair:prerequisites){
            int depc=pair[0];
            int prec=pair[1];
            if(array[prec]==null){
                array[prec]=new ArrayList<Integer>();
            }
            array[prec].add(depc);
        }
        int []visited=new int[n];
        for(int i=0;i<n;i++){
            //init visited
            for(int j=0;j<n;j++){
                visited[j]=0;
            }
            if(dfs(i,visited, array)){
                return false;
            }
        }
        return true;
    }
    private boolean dfs(int n,int[] visited,  List<Integer>[] array){
        if(visited[n]==1){
            return true;
        }
        visited[n]=1;
        if (array[n] != null) {
            for(int c:array[n]){
                if(dfs(c,visited,array)){
                    return true;
                }
            }
        }
        return false;
    }

  • 0
    L

    because this step:
    for(int c:array[n])


  • 5
    L

    Another DFS implementation with comments. A spare array onStack is used to better signal the intention of checking a back edge.

    public class Solution {
      public boolean canFinish(int num, int[][] mat) {
        Map<Integer, Set<Integer>> dependOn = new HashMap<>();
        for (int[] edge : mat) {
          int child = edge[0];
          int parent = edge[1];
          dependOn.putIfAbsent(child, new HashSet<Integer>());
          dependOn.get(child).add(parent);
        }
    
        boolean[] visited = new boolean[num];
        boolean[] onStack = new boolean[num];
        for (int i = 0; i < num; i++) {
          if (!visited[i]) { // find one not visited and start from it
            if (!dfs(dependOn, i, visited, onStack))
              return false;
          }
        }
    
        return true;
      }
    
      boolean dfs(Map<Integer, Set<Integer>> dependOn, int current, boolean[] visited, boolean[] onStack) {
        onStack[current] = true; // mark current on the stack of a post-order traversal
        for (int parent : dependOn.getOrDefault(current, new HashSet<Integer>())) {
          if (onStack[parent]) // one of the dependency is still not popped from the stack
            return false;
          if (!visited[parent] && !dfs(dependOn, parent, visited, onStack))
            return false;
        }
        visited[current] = true; // can also be placed before visiting children, so place is not important
        onStack[current] = false; // making DFS a post-order traversal: popping current when all its children are done
        return true;
      }
    }
    

  • 0

    Thanks for brilliant idea and concise codes;

    For this code segment:

    for(int i=0; i<prerequisites.length;i++){
        degree[prerequisites[i][1]]++;
        graph[prerequisites[i][0]].add(prerequisites[i][1]);
    }
    

    What you are doing is recording the courses prerequisites and drawing the map.

    for(int[] require : prerequisites){
         in_degree[require[0]] ++;
         graph[require[1]].add(require[0]);
    }
    

    However, I think this might be a little bit more understandable for someone (like me): the in_degree denotes the in-coming courses for each course and I believe that it makes more sense that when every in-coming course is taken, the course can be took. You solution is when every out-going course is taken, the course itself can be took.

    Nothing original, just a small trick.


Log in to reply
 

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