Hi I am Saurav Kumar Gupta - Flutter Developer - MobbyPark | LinkedIn
I'm a Postgraduate Student currently undertaking a Master's course in Computer Application
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 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.
Figure 1. An example of Topological Sort.
There are two ways to implement it: Breadth-First-Search (BFS) and Depth-First-Search (DFS).
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:
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:
node = queue.dequeue()
for neighbour in neighbours[node]:
indegree[neighbour] -= 1
if indegree[neighbour] == 0:
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.
Figure 2. Topological Sort with DFS.
for each node:
if visited[node] is False:
visited[node] = True
for nei in neighbours[node]: