Topological Sort Theory

Problem

Given a directed acyclic graph (DAG) produce a linear ordering of vertices such that for every edge u→v, u appears before v. Non-uniqueness arises when independent subgraphs can be interleaved.

Kahn's Algorithm

• Compute initial in-degrees.
• Maintain queue of in-degree 0 vertices.
• Remove (output) a vertex, decrement neighbors, enqueue new zeros.
• If leftover vertices have nonzero in-degree ⇒ cycle.

DFS Method

• Run DFS; push vertex to stack upon finish.
• Reverse postorder yields topological order in DAG.
• Track recursion stack or colors to detect back edge (cycle).

Data Structures

• Adjacency list: Outgoing edges.
• inDeg[v]: Remaining prerequisites count.
• Queue: Ready vertices (in-degree 0).
• Order array: Progressive linearization.

Pseudocode (Kahn)

1KAHN_TOPO(G=(V,E)):
2  inDeg[v] = 0 for v in V
3  for each (u→v) in E: inDeg[v]++
4  Q = queue of all v with inDeg[v]=0
5  order = []
6  while Q not empty:
7    u = pop(Q)
8    append u to order
9    for each (u→w) in Adj[u]:
10      inDeg[w]--
11      if inDeg[w] == 0: push w
12  if |order| < |V|: return "cycle detected"
13  return order

Complexity

Each edge reduces some in-degree exactly once.

Cycle Detection

• Kahn: leftover vertices after queue exhaustion ⇒ cycle.
• DFS: encountering gray (in-stack) vertex ⇒ back edge.

Edge Cases

• Multiple valid orders — any is acceptable.
• Disconnected DAG components handled naturally.
• Self-loop instantly implies cycle.