207. Course Schedule

Description

See: https://leetcode.com/problems/course-schedule/

Solution

This is a graph question. To be a valid course schedule the graph will need to be a directed acycle graph (DAG). If a cycle is found then the course schedule is NOT valid.

There are two solutions to this problem:

• DFS

• Kahn's algorithm

DFS Solution

DFS tranversal can be used to walk the graph and detect any cycles. The DFS algorithm is modified to keep track of the status of a vertex. The statuses are:

• Not visited

• Processing

• Processed

Invalid Course Schedule

When traversing the graph, if a vertex is found to be in "Processing" status then a cycle has been detected.

For example, assume the following class schedule [[0, 1], [1, 0]]. Here the class schedule says:

• class 0 has a prerequisite of class 1

• class 1 has a prerequisite of class 0

So, there is a cycle. When traversing the graph, we will visit vertex 0, traverse to vertex 1 and then back to vertex 0. Because vertex 0 is in status "processing" a cycle is detected.

Now we are in a cycle because course 1 has a prerequisite of course 0 (which is in status "processing"). So the algorithm can stop because we now know the course schedule is invalid.

Valid Course Schedule

If the algorithm does not encounter any vertices with "processing" status, then there are not cycles and the course schedule is valid.

Example: assume the following course schedule: [[0,1], [1,2]]. This means:

• Course 0 has a prerequisite of Course 1

• Course 1 has a prerequisite of Course 2

Here there are no cycles. So, when following the edges from a vertex we will not encounter a vertex in "processing status". If we come across a vertex that has status "processed" then we can skip it. We have already traversed it and found it to be valid. So there is no point in processing it again.

Algorithm

from collections import defaultdict
from typing import List
from enum import Enum


class Status(Enum):
    NOT_VISITED = 0
    PROCESSING = 1
    PROCESSED = 2


class Solution:

    def dfs(self, start, course_graph, visited) -> bool:
        # We will keep track of the status of each vertex. If we come across a processed vertex then we can exit as we don't need to reprocess it
        if visited[start] == Status.PROCESSED:
            return True
        # If we come across a vertex that is marked as "processing" then we have encountered a cycle. We are currently processing that vertex and one of its edges led back to it! So, we can return False as it is not a valid course schedule
        if visited[start] == Status.PROCESSING:
            return False
        visited[start] = Status.PROCESSING
        # defaultdict will automatically add a key if it is not found in the dict. The if statement is here to prevent a key from being added if it does not exist
        if start in course_graph:
            for node in course_graph[start]:
                if not self.dfs(node, course_graph, visited):
                    # we enountered a vertex that was in processing status. So a cycle exits. Return False as the course prerequisites are not valid.
                    return False
        # If we make it here then a cycle did not exist and the course prerequistes are valid.
        # Mark the vertex as processed so we do not prcess it again. We've determined this course has valid prerequisites.
        visited[start] = Status.PROCESSED
        return True

    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # create a graph where the keys are the courses and the values are the prerequisites for each course
        course_graph = defaultdict(list)
        for course, prereq in prerequisites:
            course_graph[course].append(prereq)

        visited = [Status.NOT_VISITED] * numCourses

        # every key needs to be traversed because the graph may be disconnected
        for key in course_graph:
            if not self.dfs(key, course_graph, visited):
                return False

        return True

Kahn's Algorithm Solution

Kahn's Algorithm can also be used to detect a valid course schedule.

from collections import defaultdict, deque
from typing import List
class Solution:
    
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # create a graph where the keys are the courses and the values are the prerequisites for each course
        course_graph = defaultdict(list)
        # this array keeps track of how many edges are incoming to a vertex (how many dependecies a course has)
        # because the course ids are 0 <= a, b <= numCourses, array index is course id 
        incoming_edges = [0] * numCourses

        # populate the incoming_edges with the number of prerequisites for each course
        for course, prereq in prerequisites:
            course_graph[prereq].append(course)
            incoming_edges[course] += 1


        # initialize the queue with any courses that do NOT have any prerequisites
        processing_queue = deque()
        for course, prereq in enumerate(incoming_edges):
            if prereq == 0:
                processing_queue.append(course)

        # we don't need a topological ordering for this scenario. We just need to know if the schedule is valid or not
        # so just keep track of the number of classes processed. If it differs from the graph size then the schedule is
        # invalid
        num_classes_processed = 0
        while processing_queue:
            num_classes_processed += 1
            course = processing_queue.pop()
            for dependency in course_graph[course]:
                incoming_edges[dependency] -= 1
                if incoming_edges[dependency] == 0:
                    processing_queue.append(dependency)
        return num_classes_processed == numCourses