Graph Algorithm: Topological Sort

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

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.

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 neigobours[node]:
		dfs(node)
	ret.insert(0,node)

References

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments