Data Structures & Algorithms (Graphs): Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also 
have finished course 1. So it is impossible.

Solve Here: Leetcode 207

Intuition

Let's suppose you're pursuing a Computer Science degree, and the curriculum consists of the following courses:

{
    1: "Programming Basics",
    2: "Data Structure",
    3: "Algorithms",
    4: "Operating Systems",
    5: "Machine Learning"
}

The prerequisite requirements are as follows:

Q. Is it possible to complete all the courses given these prerequisite relationships?

A. If the prerequisite relationships can be modelled as a directed graph, where each course is a node and each prerequisite is a directed edge, there exists a possible way to complete all the courses.

Programming Basics
        |
        v
Data Structures
      /     \
     v       v
Algorithms  Operating Systems
     |
     v
Machine Learning

Cycle Detection Approach: Depth-First Search

NOTE: A graph may consist of multiple disconnected components, meaning some courses may have no prerequisites and are not prerequisites of any other course. Hence, we cannot rely on a single DFS traversal to visit every node. We need to iterate over all courses and initiate DFS from every unvisited node. This ensures that every connected component in the graph is explored.

Algorithm

The edge list can be converted in an adjancy list to explore graph effectively.

During the traversal, each course can be in one of the following three states:

1. Unvisited (0): The course has not been explored yet.
2. Visiting (1): The course is in the current DFS path.
3. Visited (2): The course and all its prerequisites have already been explored.

We can use recursion to perform DFS.

Hypothesis

Let DFS(currentCourse) be the recursive function that explores all courses reachable from currentCourse. The function returns:

• true if a cycle is detected anywhere in the DFS subtree rooted at currentCourse.
• false if the entire subtree rooted at currentCourse can be explored without encountering a cycle.

Recursive Steps

// 1. Process the currentCourse
graph[currentCourse].state = 'VISITING';

// 2. Explore all prerequisites
for each prerequisite in graph[currentCourse].prerequisites:
    // if prerequisite is unvisited
    if prerequisite.state == 'UNVISITED':
        // perform DFS on the prerequisite
        boolean hasCycle = DFS(prerequisite);
        if (hasCycle): return true;

// 3. Entire subtree rooted at currentCourse has been explored without encountering a cycle.
graph[currentCourse].state = 'VISITED';
return false; 

Base Conditions

// 1. If prerequisite is already in the current DFS recursion stack
if prerequisite.state == 'VISITING': return true;

// 2. if prerequisite is already explored, ignore it 
if prerequisite.state == 'VISITED': continue;

Implementation

class Solution {

    private boolean hasCycle(Map<Integer, List<Integer>> graph, int[] state, int currentCourse) {

        // Base Condition 1: If the currentCourse is in 'Visiting' state, a cycle has been detected.
        if(state[currentCourse] == 1) {
            return true;
        }

        // Base Condition 2: If the currentCourse is in 'Visited' state, its subtree is alread explored and no cycle was detected.
        if(state[currentCourse] == 2) {
            return false;
        }

        // Recursive Steps

        // 1. Mark the currentCourse as 'Visiting'
        state[currentCourse] = 1;

        // 2. Explore all its prerequisites
        for(int prerequisite: graph.get(currentCourse)) {
            boolean containsCycle = hasCycle(graph, state, prerequisite);
            if(containsCycle) return true;
        }

        // 3. Mark the currentCourse state as 'Visited'.
        state[currentCourse] = 2;
        return false;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {

        // 1. Create an adjacency list using the prequisites edge list to represent the directed graph
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for(int key = 0; key < numCourses; key++) {
            graph.put(key, new ArrayList<>());
        }

        for(int[] edge: prerequisites) {
            graph.get(edge[0]).add(edge[1]);
        }

        // 2. Define a array to store the states (0/1/2) of each course.
        //    0 -> Unvisited, 1 -> Visiting, 2 -> Visited 
        int[] state = new int[numCourses];

        // 3. Iterate over all courses and perform DFS on the unvisited courses
        for(int course: graph.keySet()) {
            if(state[course] == 0) {
                if(hasCycle(graph, state, course)) {
                    return false;
                }
            }
        }

        return true;
 
    }
}

Visualization

Time Complexity

The work done by all DFS calls is shared across the graph rather than repeated for every starting node. Across the entire algorithm:

• Every course is processed at most once: O(V)
• Every prerequisite relationship is examined at most once: O(E)

Hence, the overall time complexity is O(E + V).

Space Complexity

The algorithm uses additional memory for three data structures:

• The adjacency list: O(E + V)
• The state array: O(V)
• The recursion stack: O(V)

Hence, the overall space complexity is O(E + V).

Topological Sort Approach (Kahn's Algorithm): Breadth-First Search

Algorithm

If we represent the directed graph as an adjacency list with following key-value pairs: {course -> list of prerequisites}, then post removing a course with no prerequisites, we may have to update the list of prerequisites for other courses.

For example, consider the following graph:

{
    Programming Basics : [],
    Data Structures    : [Programming Basics],
    Algorithms         : [Data Structures],
    Operating Systems  : [Data Structures]
}

After completing Programming Basics, Data Structures should no longer list it as a prerequisite. To update the graph, we would have to iterate over the list of prerequisites of every course, searching for Programming Basics and removing it wherever it appears. This operation would take O(V+E) time for every course we remove, making the overall algorithm inefficient.

Instead, if we represent the graph as {prerequisite -> list of dependent courses} and use an array to store the count of prerequisites (also called in-degree) for each course, we can efficiently:

• Identify a course which is currently eligible to be taken (in-degree == 0)

• Iterate over its dependent courses and decrement their in-degree by 1. If the in-degree of any dependent course becomes 0, it means all of its prerequisites have been completed, making it eligible to be taken next.

The mental model shifts from "for a course to be completed, all its prerequisities must be completed" to "if the prerequisite is completed, all its dependent courses may become eligible for completion".

We can use a queue to store the courses that are currently eligible to be taken.

1. Build adjacency list (prerequisite -> list of dependent courses)
2. Build in-degree array (course -> in-degree)
3. Initialize a queue with courses that have in-degree == 0
4. While queue is not empty:
    - Dequeue a course
    - Iterate over its dependent courses and decrement their in-degree by 1
    - If the in-degree of any dependent course becomes 0, enqueue it
5. If the number of courses completed is equal to the total number of courses, return true
6. Otherwise, return false

NOTE: Notice that all courses at the current level are processed before moving on to the next level, which is exactly the behavior of a Breadth First Search.

Implementation

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {

        // 1. Create adjacency list for {prerequisite -> list of dependent courses}
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        for(int key = 0; key < numCourses; key++) {
            adjList.put(key, new ArrayList<>());
        }

        int[] indegree = new int[numCourses];
        for(int[] edge: prerequisites) {
            int course = edge[0];
            int prerequisite = edge[1];

            adjList.get(prerequisite).add(course);
            indegree[course]++;
        }

        // 2. Initialize a queue with all the courses having in-degree = 0.
        Queue<Integer> queue = new LinkedList<>();
        for(int course = 0; course < numCourses; course++) {
            if(indegree[course] == 0) {
                queue.offer(course);
            }
        }

        int completedCourses = 0;

        // 3. Traverse the directed graph
        while(!queue.isEmpty()) {
            int currentCourse = queue.poll();
            completedCourses++;

            // Iterate over the currentCourse dependent courses and decrement their in-degree by 1.
            for(int dependentCourse: adjList.get(currentCourse)) {
                indegree[dependentCourse]--;
                // If in-degree of dependentCourse = 0, it is eligible for completion 
                if(indegree[dependentCourse] == 0) {
                    queue.offer(dependentCourse);
                }
            }
        }

        // 4. If completedCourses = numCourses, every course for traverse and no cycle was detected.
        if(completedCourses == numCourses) return true;
        return false;

    }
}

Visualization

Time Complexity

The algorithm performs the following operations:

1. Building the adjacency list: We iterate over the prerequisites edge list once. This takes O(E) time.

2. Building the in-degree array: While building the adjacency list, we also build the in-degree array. This takes O(E) time.

3. Initializing the queue: In the worst case, all courses have in-degree == 0. This takes O(V) time.

4. Traversing the graph: Each course is processed once and for each course, we iterate over its dependent courses (prerequisite relationships). This takes O(V + E) time.

Hence, the overall time complexity is O(V + E).

Space Complexity

The algorithm uses additional memory for three data structures:

1. The adjacency list: Stores one entry for every course (V vertices) and one entry for every prerequisite relationship (E edges). This takes O(E + V) space.

2. The in-degree array: Stores one entry for every course (V vertices). This takes O(V) space.

3. The queue: In worst case, it may store one entry for every course (V vertices). This takes O(V) space.

Hence, the overall space complexity is O(E + V).