Description

Topological sort is just a Directed graph with no cycles traversed with a variant of BFS which only puts nodes on the queue, whenever all their parent nodes have been explored.
?

Reach for when

You need to check that things are done in a certain order with each parent getting completed first.

Runtime

O(n^2)

Visualization

Pseudocode

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edge

while S is not empty do
    remove a node n from S
    add n to L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S

if graph has edges then
    return error   (graph has at least one cycle)
else
    return L   (a topologically sorted order)

Code

from collections import deque

def topological_sort(graph, n):
	# graph = {node: [children]}, nodes labeled 0..n-1
	indegree = [0] * n
	for node in graph:
		for child in graph[node]:
			indegree[child] += 1          # count each node's prerequisites

	queue = deque(x for x in range(n) if indegree[x] == 0)  # parent-less nodes
	order = []

	while queue:
		node = queue.popleft()
		order.append(node)
		for child in graph[node]:
			indegree[child] -= 1          # "remove" the edge node -> child
			if indegree[child] == 0:      # child's prerequisites are all done
				queue.append(child)

	if len(order) < n:                    # not every node placed → a cycle exists
		return None
	return order