Topological ordering

What are graph ordering and connectivity?

Graph ordering asks which sequence respects the connections in a graph. Connectivity asks which vertices can reach one another. For prerequisite relationships, a topological order puts each prerequisite before the task that needs it. It exists only when the directed graph has no cycle.

Example: If task A must finish before B, and B before C, A, B, C is a valid order. Adding a requirement that C must finish before A creates a cycle, so no such order exists.

Helpful before this chapter

If these ideas are new, begin with:

Graph representations and traversal

Understand the idea

A topological order places every prerequisite before its dependent. It exists exactly for directed acyclic graphs. Kahn uses indegrees to select vertices whose prerequisites have all been removed. An indegree decrement occurs once for each removed incoming edge. Isolated vertices begin ready. If duplicate edges are represented, both adjacency entries and indegree increments must count them consistently.

Work through an example

Edges 0→1,0→2,1→3,2→3 allow [0,1,2,3] or [0,2,1,3]. A queue's order chooses one, not necessarily a unique answer.

Time and space complexity

O(V+E) time/O(V+E) graph storage plus O(V) working state.

Why it works

Current indegree counts incoming edges from unprocessed vertices.

Common mistakes

Reverse edge direction reverses dependency meaning.
Sorting vertex labels alone ignores edges.

Chapter lab · Python implementation

Dependency order and connectivity answer different questions. Kahn topological sorting removes zero-indegree vertices from a directed graph. Disjoint-set union merges undirected connectivity groups without maintaining paths. The lab implements both; choose the structure whose contract matches the question.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

from collections import deque

def topological(n,edges):
    graph=[[] for _ in range(n)]; indegree=[0]*n
    for a,b in edges:
        graph[a].append(b); indegree[b]+=1
    queue=deque(i for i in range(n) if indegree[i]==0)
    order=[]
    while queue:
        a=queue.popleft(); order.append(a)
        for b in graph[a]:
            indegree[b]-=1
            if indegree[b]==0: queue.append(b)
    return order if len(order)==n else None

class DSU:
    def __init__(self,n):
        self.parent=list(range(n)); self.size=[1]*n
    def find(self,x):
        while x!=self.parent[x]:
            self.parent[x]=self.parent[self.parent[x]]
            x=self.parent[x]
        return x
    def union(self,a,b):
        a,b=self.find(a),self.find(b)
        if a==b: return False
        if self.size[a]<self.size[b]: a,b=b,a
        self.parent[b]=a; self.size[a]+=self.size[b]
        return True

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert topological(4,[(0,1),(0,2),(1,3),(2,3)])==[0,1,2,3]
assert topological(2,[(0,1),(1,0)]) is None
d=DSU(4); assert d.union(0,1) and d.union(1,2)
assert d.find(0)==d.find(2) and not d.union(0,2)
assert d.find(3)!=d.find(0)

CHECK YOUR UNDERSTANDING

What are graph ordering and connectivity?

Only 0 has no unmet prerequisites.