# 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

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 defaultdictclass 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 []`