Comment on page

# 207. 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 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

1
from collections import defaultdict
2
from typing import List
3
from enum import Enum
4
5
6
class Status(Enum):
7
NOT_VISITED = 0
8
PROCESSING = 1
9
PROCESSED = 2
10
11
12
class Solution:
13
14
def dfs(self, start, course_graph, visited) -> bool:
15
# 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
16
if visited[start] == Status.PROCESSED:
17
return True
18
# 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
19
if visited[start] == Status.PROCESSING:
20
return False
21
visited[start] = Status.PROCESSING
22
# 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
23
if start in course_graph:
24
for node in course_graph[start]:
25
if not self.dfs(node, course_graph, visited):
26
# we enountered a vertex that was in processing status. So a cycle exits. Return False as the course prerequisites are not valid.
27
return False
28
# If we make it here then a cycle did not exist and the course prerequistes are valid.
29
# Mark the vertex as processed so we do not prcess it again. We've determined this course has valid prerequisites.
30
visited[start] = Status.PROCESSED
31
return True
32
33
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
34
# create a graph where the keys are the courses and the values are the prerequisites for each course
35
course_graph = defaultdict(list)
36
for course, prereq in prerequisites:
37
course_graph[course].append(prereq)
38
39
visited = [Status.NOT_VISITED] * numCourses
40
41
# every key needs to be traversed because the graph may be disconnected
42
for key in course_graph:
43
if not self.dfs(key, course_graph, visited):
44
return False
45
46
return True
47

### Kahn's Algorithm Solution

Kahn's Algorithm can also be used to detect a valid course schedule.
1
from collections import defaultdict, deque
2
from typing import List
3
class Solution:
4
5
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
6
# create a graph where the keys are the courses and the values are the prerequisites for each course
7
course_graph = defaultdict(list)
8
# this array keeps track of how many edges are incoming to a vertex (how many dependecies a course has)
9
# because the course ids are 0 <= a, b <= numCourses, array index is course id
10
incoming_edges = [0] * numCourses
11
12
# populate the incoming_edges with the number of prerequisites for each course
13
for course, prereq in prerequisites:
14
course_graph[prereq].append(course)
15
incoming_edges[course] += 1
16
17
18
# initialize the queue with any courses that do NOT have any prerequisites
19
processing_queue = deque()
20
for course, prereq in enumerate(incoming_edges):
21
if prereq == 0:
22
processing_queue.append(course)
23
24
# we don't need a topological ordering for this scenario. We just need to know if the schedule is valid or not
25
# so just keep track of the number of classes processed. If it differs from the graph size then the schedule is
26
# invalid
27
num_classes_processed = 0
28
while processing_queue:
29
num_classes_processed += 1
30
course = processing_queue.pop()
31
for dependency in course_graph[course]:
32
incoming_edges[dependency] -= 1
33
if incoming_edges[dependency] == 0:
34
processing_queue.append(dependency)
35
return num_classes_processed == numCourses