Scheduling

Topological Sort

Linear ordering of vertices in a Directed Acyclic Graph (DAG) respecting dependency constraints.

What is Topological Sort?

Topological Sorting of a directed acyclic graph (DAG) is a linear ordering of its vertices such that for every directed edge u -> v, vertex u comes before v in the ordering. Kahn's Algorithm is a queue-based topological sort that iteratively removes vertices with zero in-degree (no incoming dependencies) and updates their neighbors.

Key Characteristics:

  • Only works on Directed Acyclic Graphs (DAGs).
  • If a graph has cycles, topological sorting is impossible.
  • Kahn's Algorithm uses in-degree tracking.
  • Essential for task scheduling, compilers, and package managers.

Complexity Analysis

Avg Time Complexity: O(V + E) where V is vertices and E is edges
Space Complexity: O(V) in-degree array and queue storage
Best Case: O(V + E)
Worst Case: O(V + E)

How it Works Step-by-Step

  1. Calculate In-Degrees: Compute the number of incoming edges for all vertices.
  2. Queue Init: Insert all vertices with in-degree equal to 0 into a queue.
  3. Extract & Record: Pop vertex u from queue, append it to result sequence.
  4. Relax Neighbors: For each outgoing edge u -> v, decrement in-degree of v. If in-degree of v becomes 0, push it into the queue.
  5. Acyclicity Check: If output contains fewer than V nodes, the graph has a cycle.

Code Implementation

Worked Trace Example

DAG with edges: A->B, A->C, B->D, C->D. 4 nodes:
1. In-degrees: A=0, B=1, C=1, D=2. Queue = [A].
2. Pop A: result = [A]. Decrement neighbors: B in-degree=0, C in-degree=0. Queue = [B, C].
3. Pop B: result = [A, B]. Decrement neighbor D: D in-degree=1.
4. Pop C: result = [A, B, C]. Decrement neighbor D: D in-degree=0. Queue = [D].
5. Pop D: result = [A, B, C, D]. Queue empty.
Result: Valid topological order A -> B -> C -> D.

Ready to Understand Topological Sort Visually?

Don't just read about it. Launch our interactive, premium algorithm visualizer to step through calculations in real-time.

Launch Topological Sort Visualizer →