Course Schedule and Topological Sorting

Intro

Let’s start with a leetcode problem, link here:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Topological Sorting

Course schedule

Back to this leetcode problem, it can be solved by topological sorting. And similar to this sorting algorithm, we use a stack and a set to store the result and to mark the visited vertices.

from collections import defaultdict
class Solution:
WHITE = 1
GRAY = 2
BLACK = 3
def findOrder(self, numCourses, prerequisites):
# Create the adjacency list representation of the graph
adj_list = defaultdict(list)
# A pair [a, b] in the input represents edge from b --> a
for dest, src in prerequisites:
adj_list[src].append(dest)
topological_sorted_order = []
is_possible = True
# By default all vertces are WHITE
color = {k: Solution.WHITE for k in range(numCourses)}
def dfs(node):
nonlocal is_possible
# Don't recurse further if we found a cycle already
if not is_possible:
return
# Start the recursion
color[node] = Solution.GRAY
# Traverse on neighboring vertices
if node in adj_list:
for neighbor in adj_list[node]:
if color[neighbor] == Solution.WHITE:
dfs(neighbor)
elif color[neighbor] == Solution.GRAY:
# An edge to a GRAY vertex represents a cycle
is_possible = False
# Recursion ends. We mark it as black
color[node] = Solution.BLACK
topological_sorted_order.append(node)
for vertex in range(numCourses):
# If the node is unprocessed, then call dfs on it.
if color[vertex] == Solution.WHITE:
dfs(vertex)
return topological_sorted_order[::-1] if is_possible else []

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store