Detailed solution + analysis - DFS Java


  • 0

    High level solution overview:

    1. Construct a graph from the set of prerequisite courses.
    2. Use Depth first search (DFS) to search for cycles in course requirements. If there are no cycles in the graph, then the courses can be taken.

    Graph representation : (Adjacency list)
    We convert the list of course pairs to a directed graph with an edge u->v that represents a "pre-requisite to" relationship. Thus if we have the pair [0,1] (1 is a pre-requisite to 0), then we will have the following edge in our graph : 1->0
    Note: We consider the adjacency list representation over an adjacency matrix, considering that the graph might be sparse.

    private List<List<Integer>> buildGraph(int numCourses, int[][] prereqs) {
            List<List<Integer>> g = new ArrayList<>();
            for(int i = 0; i < numCourses; i++) {
                g.add(new ArrayList<>());
            }
            
            for(int[] prereq : prereqs) {
                int courseRequiredBefore = prereq[1];
                int course = prereq[0]; //edges will be from courseReqdBefore -> course
                List<Integer> coursesSubsequentTo = g.get(courseRequiredBefore);
                coursesSubsequentTo.add(course);
            }
            
            return g;
    }
    

    Recursive Cycle detection: (DFS)
    To detect a cycle from a particular node v in the graph, we run DFS on that node in order to find the set of all vertices reachable from v. If we find that v appears again in our search, we know that there is a cycle that starts and ends at v.
    Data structures required :
    a) visited array - to keep track of vertices already visited
    b) set - to keep track of vertices visited. Consider this as parallel to the recursion stack. We use a set specially to get O(1) search capability.

    //stackSet - parallel DS to recursion stack - faster search
        private boolean hasCycle(int v, List<List<Integer>> g, boolean[] visited, Set<Integer> stackSet) { 
            if(visited[v]) {
                return stackSet.contains(v);
            }
            
            visited[v] = true;
            stackSet.add(v);
            
            for(int u : g.get(v)) {
                if(hasCycle(u, g, visited, stackSet)) {
                    return true;
                }
            }
            
            stackSet.remove(v); //set maintenance - have to remove in order to maintain stack parallelism
            
            return false;
        }
    

    Now, since the graph may not necessarily be connected, we need to run cycle detection on all nodes.
    Note: If a node is already visited, we need not detect cycles on it any further as we already have detected cycles on it.

    public boolean canFinish(int numCourses, int[][] prerequisites) {
            List<List<Integer>> g = buildGraph(numCourses, prerequisites);
            boolean[] taken = new boolean[numCourses];
            for(int v = 0; v < g.size(); v++) {
                if(!taken[v]) {
                    Set<Integer> stackSet = new HashSet<>();
                    if(hasCycle(v, g, taken, stackSet)) {
                        return false;
                    }
                }
            }
            
            return true;
        }
    

    Complexity analysis
    n: number of course requisite pairs = no of vertices in the graph
    e: number of pre-requisite-to relationships = no of edges in the graph

    1. buildGraph - O(n) time, O(n + e) space (space complexity of adjacency list representation - directed graphs).
      Creating an empty array list takes O(1) time and creating n such lists will take O(n) time. Traversing the set of course pairs and populating the adjacency list will take O(n) time as get and add operations on array lists take O(1) time and O(1) amortized time respectively. Thus it would take O(n + n) time ~ O(n) time.

    2. hasCycle - O(n + e) time (time complexity of DFS), O(n) - space
      Since set operations get and add operations take O(1) time, there is no additional cost incurred in our standard DFS implementation. Thus the time complexity is O(n + e).
      Since we are using a parallel set to the recursion stack, the space complexity is at most O(2n) (n for the recursion stack and n for the set) ~ O(n).

    Considering 1 and 2, the total time complexity is ~ O(n + e) and the total space complexity is ~ O(n + e)


Log in to reply
 

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