Comment on page

# 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 1yr ago