Topological Sorting for Directed Acyclic Graphs (DAGs)

Topological Sorting

Topological sorting produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every edge (u, v), vertex u comes before vertex v. It is only defined for DAGs — graphs with directed edges and no cycles.

Kahn's Algorithm (BFS-based)

1. Compute the in-degree of every node
2. Add all nodes with in-degree 0 to a queue
3. While the queue is not empty:
   • Dequeue node u, add it to the result
   • For each neighbor v of u, decrement v's in-degree
   • If v's in-degree becomes 0, enqueue v
4. If the result contains all nodes, the sort is valid; otherwise, the graph has a cycle

In-degrees: A=0, B=1, C=1, D=2
Queue: [A] → process A, decrement B and C
Queue: [B, C] → process B, decrement D
Queue: [C] → process C, decrement D
Queue: [D] → process D
Result: [A, B, C, D]

DFS-based Algorithm

1. Run DFS and record the finish time of each node
2. Sort nodes in reverse finish time order
3. This produces a valid topological ordering

Multiple Valid Orderings

A DAG may have many valid topological orderings. For example, if A → C and B → C, both [A, B, C] and [B, A, C] are valid because A and B have no dependency on each other.

Time Complexity

Both algorithms run in O(V + E) time.

Detecting Cycles

If you run Kahn's algorithm and the result has fewer nodes than the graph, the remaining nodes form a cycle. This is a useful cycle detection method for directed graphs.