Course Schedule and Topological Sorting

3 min readOct 30, 2020


My last post introduced the definition of the graph. The graph can be built and applied to many scenarios. In this post, I’ll introduce one of its applications: topological sorting.


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

There are a total of n courses you have to take labelled from 0 to n - 1.

Some courses may have prerequisites, for example, if prerequisites[i] = [ai, bi] this means you must take the course bi before the course ai.

Given the total number of courses numCourses and a list of the prerequisite pairs, return the ordering of courses you should take to finish all courses.

If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

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].

Example 2:

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].

In order to know the course schedule, we must know a ‘path’ starting from the first course which doesn’t need any prerequisites, to the course that doesn’t have any ‘child’. Actually, each pair in the prerequisites can be seen as a vertice in a directed graph: it origins from the second element, end at the first element in the pair. In order to solve this problem, we’ll introduce a definition called Topological Sorting.

Topological Sorting


In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

The following graph will give an example of topological sorting:

In this case, we have a set to store visited vertices, and a stack to store the result. We start with an arbitrary vertice in the graph, then check if it has any ‘children’ vertice until the vertice runs out. Then we gradually put vertice in the stack. If the current path is included, we arbitrary choose the unvisited vertice to do it again until we visited all vertices in this graph.

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:
GRAY = 2
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:
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:
# 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:
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
for vertex in range(numCourses):
# If the node is unprocessed, then call dfs on it.
if color[vertex] == Solution.WHITE:
return topological_sorted_order[::-1] if is_possible else []

Thanks for reading!




on the way to become a programmer