Topological Sort

Kahn's algorithm and DFS-based topological ordering for DAGs.

6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Kahn's Algorithm (BFS)

Compute indegree of all nodes. Queue nodes with indegree 0. Process queue: remove node, add to result, decrement indegree of neighbors. If neighbor indegree becomes 0, enqueue. If result size < V, cycle exists.

Gokahn's-topological-sort.go

37 linesLn 1, Col 1Go

Indegree 0 nodes have no prerequisites. Process them, reduce prerequisites for dependents. Cycle detection: if not all nodes processed, cycle exists.

DFS-based Topological Sort

DFS post-order traversal. Add node to result after visiting all children. Reverse result. Need cycle detection (Gray state).

Godfs-topological-sort-with-cycle-detection.go

38 linesLn 1, Col 1Go

DFS post-order (add after children). Reverse gives topological order. Gray state detects cycles (back edge).

Applications

Course scheduling: Prerequisites → topological order.
Build systems: Dependencies between modules.
Task scheduling: Dependencies between tasks.
Alien dictionary: Infer alphabet order from sorted words.
Parallel execution: Independent tasks can run in parallel.

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.