🎓 A1Learner
🔍

DSA Topological Sort

A topological sort lists the vertices of a directed graph so every edge points forward. Kahn's algorithm builds that order by removing vertices with no incoming edges.

Counting indegrees

Course 3 waits on two prerequisites. Its indegree prints as two below.

pairs = [(1, 0), (2, 0), (3, 1), (3, 2)]
indegree = {i: 0 for i in range(4)}
for course, prereq in pairs:
    indegree[course] += 1
for v in sorted(indegree):
    print(v, indegree[v])

Removing zero-indegree vertices

Vertex 0 leaves first and frees its neighbours. The freed vertices join the back of the queue.

from collections import deque

pairs = [(1, 0), (2, 0), (3, 1)]
graph = {i: [] for i in range(4)}
indegree = {i: 0 for i in range(4)}
for course, prereq in pairs:
    graph[prereq].append(course)
    indegree[course] += 1
for v in graph:
    graph[v] = sorted(graph[v])
queue = deque(sorted(v for v in indegree if indegree[v] == 0))
order = []
while queue:
    node = queue.popleft()
    order.append(node)
    for nb in graph[node]:
        indegree[nb] -= 1
        if indegree[nb] == 0:
            queue.append(nb)
print(order)

Example

from collections import deque

def topo_sort(num_courses, pairs):
    graph = {i: [] for i in range(num_courses)}
    indegree = {i: 0 for i in range(num_courses)}
    for course, prereq in pairs:
        graph[prereq].append(course)
        indegree[course] += 1
    for v in graph:
        graph[v] = sorted(graph[v])
    queue = deque(sorted(v for v in indegree if indegree[v] == 0))
    order = []
    removals = 0
    while queue:
        node = queue.popleft()
        order.append(node)
        for nb in graph[node]:
            indegree[nb] -= 1
            removals += 1
            if indegree[nb] == 0:
                queue.append(nb)
    return order, removals

order, removals = topo_sort(4, [(1, 0), (2, 0), (3, 1), (3, 2)])
print("Order one:", order)
print("Edges removed:", removals)
order, removals = topo_sort(6, [(1, 0), (2, 0), (3, 1), (4, 2), (5, 3), (5, 4)])
print("Order two:", order)
order, removals = topo_sort(3, [(1, 0), (2, 1), (0, 2)])
print("Order three:", order)
print("Stuck nodes:", 3 - len(order))

Key points

  • Topological order: a listing where each edge points from an earlier vertex to a later one
  • Indegree: the number of edges that point into one vertex
  • A vertex with indegree zero can be placed next
  • Removing a vertex lowers the indegree of each of its neighbours
  • The queue in this lesson starts sorted and neighbours are visited in sorted order
  • That fixed rule makes the printed order the same on every run
  • A graph with a cycle leaves some vertices stuck above indegree zero

In this example, Kahn's algorithm orders two course plans and rejects a third. The first plan prints the order 0, 1, 2, 3 after four edge removals. The second plan prints a full order of six courses. The third plan contains a cycle, so its order prints empty. The stuck count prints three, which names every course trapped in the cycle.

Note

A stuck vertex count above zero is the proof that no order exists.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A vertex still has indegree 2 after the queue empties. What does that mean?