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

Wikipedia:

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:
    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!