Introduction to Topological Sort
Shawn
32007
Topological SortGraph Theory

Overview

When we are scheduling jobs or tasks, they may have dependencies. For example, before we finish task a, we have to finish b first. In this case, given a set of tasks and their dependencies, how shall we arrange our schedules? There comes an interesting graph algorithm: Topological Sort.

According to Introduction to Algorithms, given a directed acyclic graph (DAG), a topological sort is a linear ordering of all vertices such that for any edge (u, v), u comes before v. Another way to describe it is that when you put all vertices horizontally on a line, all of the edges are pointing from left to right.

image

Figure 1. An example of Topological Sort.

Implementations

There are two ways to implement it: Breadth-First-Search (BFS) and Depth-First-Search (DFS).

BFS

For BFS, we need an array indegree to keep the track of indegrees. Then we will try to output all nodes with 0 indegree, and remove the edges coming out of them at the same time. Besides, remember to put the nodes that become 0 indegree in the queue.

Then, we can keep doing this until all nodes are visited. To implement it, we can store the graph in an adjacent list (a hashmap or a dictionary in Python) and a queue to loop. Pseudocode is demonstrated here:

image

Figure 2. Topological Sort with BFS.

indegree = an array indicating indegrees for each node
neighbours = a HashMap recording neighbours of each node
queue = []
for i in indegree:
    if indegree[i] == 0:
        queue.append(i)
		
while !queue.empty():
    node = queue.dequeue()
    for neighbour in neighbours[node]:
        indegree[neighbour] -= 1
        if indegree[neighbour] == 0:
            queue.append(neighbour)

DFS

The key observation is that, leaf nodes should always come after their parents and ancestors. Following this intuition we can apply DFS and output nodes from leaves to the root.

We need to implement a boolean array visited so that visited[i] indicates if we have visited vertex i. For each unvisited node, we would first mark it as visited and call DFS() to start searching its neighbours. After finishing this, we can insert it to the front of a list. After visiting all nodes, we can return that list.

image

Figure 2. Topological Sort with DFS.

def topological_sort():
    for each node:
        if visited[node] is False:
            dfs(node)

def dfs(node):
    visited[node] = True
    for nei in neighbours[node]:
		if visited(node) = false:
			dfs(node)
	ret.insert_at_the _front(node)

Here are some practices for topological sort. Feel free to give it a shot!

Comments (26)