When we are scheduling jobs or tasks, they may have dependencies, i.e., 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 another graph algorithm: Topological Sort.
What is 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.
Following this intuition, there are two ways to realize it – our old friends again – BFS and DFS.
Topological sort with BFS
For BFS, we can literally do as the definition suggests. Each time we can output the nodes with no in degrees, and while we are doing that, we would also remove the edges coming out of them. 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:
in_degree = an array indicating in degrees for each node neighbours = a HashMap recording neighbours of each node queue =  for i in in_degree: if in_degree[i] == 0: queue.append(i) while queue: node = queue.dequeue() for nei in neighbours[node]: in_degree[nei] -= 1 if in_degree[nei] == 0: queue.append(nei)
Topological sort with DFS
We need to implement a boolean array
visited so that
visited[i] indicates whether we have visited vertex i or not. 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.
def topological_sort() for each node: if visited[node] is False: dfs(node) def dfs(node): visited[node] = True for nei in neigobours[node]: dfs(node) ret.insert(0,node)
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.