Topological Sorting And Cycle Detection
Asked of: Software Engineer
Last updated
What's being tested
Candidates must model dependency graphs and produce a valid Topological sort when possible, or detect a cycle that makes ordering impossible. Interviewers probe graph representation choices, algorithm selection (Kahn vs DFS), correctness, and edge-case handling like self-dependencies and disconnected nodes.
Patterns & templates
-
Kahn's algorithm — build an adjacency list + in-degree array, use
collections.deque, process zero in-degree nodes; time O(V+E), space O(V+E). -
DFS-based topological sort — run
DFS, push nodes to output on post-order; detect back-edges with a recursion stack for cycle detection. -
Represent graph with a dict of lists or vector-of-vectors for sparse graphs; avoid O(V^2) adjacency matrices unless V is tiny.
-
Handle nodes with no edges explicitly: include all vertices in the initial data structures to produce complete orderings.
-
For multiple valid orders, return any valid topological ordering and document nondeterminism; use a min-heap to produce lexicographically smallest order when required.
-
Detect cycles by comparing output length to V (
Kahn) or by encountering a node already in the recursion stack (DFS). -
Watch recursion depth for large V (~10^5); switch to iterative
DFSor increase recursion limit in languages likePython.
Common pitfalls
Pitfall: Forgetting to include isolated nodes leads to missing tasks in the result.
Pitfall: Using adjacency matrix or O(V^2) operations on V up to 10^5 causes TLE or memory blowups.
Pitfall: Not handling self-loops correctly — they are cycles and should make ordering impossible.
Practice these
The practice cards below cover the canonical variants — solve all of them and time yourself.
Practice questions
Related concepts
- Topological Sort And Cycle DetectionCoding & Algorithms
- Graph Algorithms, Dependency Resolution And ConnectivityCoding & Algorithms
- Graph, Grid, And Connectivity AlgorithmsCoding & Algorithms
- Graph Traversal, Shortest Paths, and Topological SortCoding & Algorithms
- Graph Traversal And Shortest PathsCoding & Algorithms
- Graph Search, State Space, And Path OptimizationCoding & Algorithms