207. Course Schedule
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 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
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.
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.
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
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
Last modified 4mo ago