# Course Schedule and Topological Sorting

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.

## Intro

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

anyof them. If it is impossible to finish all courses, returnan 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 sortortopological orderingof a directed graph is a linear ordering of its vertices such that for every directed edgeuvfrom vertexuto vertexv,ucomes beforevin 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: 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 []

Thanks for reading!