Introduction to Topological Sort

Overview

Implementations

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

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

Software Engineering graduate at NIT Trichy, India