This is a graph question. To be a valid course schedule the graph will need to be a . If a cycle is found then the course schedule is NOT valid.
There are two solutions to this problem:
DFS Solution
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
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
can also be used to detect a valid course schedule.