218: Topological Sorting, DAGs, Dependencies, and Strongly Connected Components

Learning outcomes

By the end of this lesson, you can:

explain and apply a DAG in a realistic implementation;
explain and apply Kahn's algorithm in a realistic implementation;
explain and apply DFS topological ordering in a realistic implementation;
explain and apply non-uniqueness in a realistic implementation;
explain and apply strongly connected components in a realistic implementation.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from a previous project where the same concern appeared: perhaps build steps, course prerequisites, workflow states, or a service dependency. The point is not to memorize a graph term. It is to make a defensible choice in both an interview-sized problem and a production data-processing problem. Start with the constraints and the failure modes, then choose the representation and algorithm that make those constraints visible.

Terminology

DAG: A directed acyclic graph is a directed graph with no directed cycle. Its edges can represent precedence, such as “A must finish before B can start.”
Kahn algorithm: Track each vertex's indegree, queue vertices with zero indegree, conceptually remove their outgoing edges, and count the vertices processed. If fewer than V vertices are processed, a cycle exists.
DFS topological order: A postorder, reversed by finish time, is a topological order when DFS finds no back edge or other cycle. Recursion-stack state or equivalent colors are needed to distinguish a back edge from an already completed branch.
Non-uniqueness: A DAG may have many valid topological orders. If several vertices have zero indegree at the same time, no single order is implied unless the requirements add a tie-breaking rule.
Strongly connected components: In a directed graph, vertices belong to the same strongly connected component when every vertex can reach every other vertex in that component.
Dependency diagnosis: A failed topological sort should identify the cycle or the nodes affected by it, rather than merely returning an empty order. An actionable error is much more useful than a boolean failure.

Mental model

When you model Topological Sorting, DAGs, Dependencies, and Strongly Connected Components, treat the work as a design problem with observable inputs, outputs, invariants, and failure modes. A directed acyclic graph encodes precedence constraints. A topological order is possible only when those constraints contain no cycle. If a cycle does exist, its structure tells you whether dependencies can be repaired directly or whether they should first be grouped into components.

The useful invariant is simple: for every directed edge u -> v, u must appear before v in the resulting order. The algorithm is responsible for producing an order that satisfies that invariant, or for providing evidence that no such order exists. A strong implementation also makes its assumptions visible, validates boundaries, and leaves enough evidence in tests, types, constraints, metrics, or diagrams to explain why the result is safe.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call. First state what must remain true, whether the graph is expected to be acyclic, whether duplicate edges are possible, and whether callers require a stable or deterministic result. Then choose the mechanism that enforces and exposes those decisions.

Deep dive

1. DAG

Suppose a build step starts before one of its prerequisites finishes, or a course is listed as depending on a later course. The problem is not just “sort these names”; the input contains directed precedence constraints, and those constraints may contradict one another. A directed acyclic graph, or DAG, is the model used when the directed graph has no directed cycle. Build systems, course prerequisites, workflow dependencies, and partial orders often form DAGs when their constraints are valid.

The absence of a cycle is the key contract. A graph such as compile -> test -> deploy can be ordered, while compile -> test -> deploy -> compile cannot. Before implementing, decide whether invalid cycles should be rejected, reported with their members, or condensed into groups for a later stage.

Decision rule: Use a DAG deliberately when it makes the contract or invariant easier to prove. If calling something a DAG merely reduces typing while hiding an assumption about the input, use the more explicit graph design and validate that assumption.

2. Kahn algorithm

Kahn's algorithm makes the prerequisite count explicit. Compute each vertex's indegree, meaning the number of incoming edges that still need to be satisfied. Put every zero-indegree vertex into a queue, remove it from consideration, decrement the indegree of its outgoing neighbors, and enqueue neighbors that become zero-indegree. The emitted sequence is valid because a vertex is emitted only after all of its prerequisites have been removed.

The cycle test is not an incidental detail: if fewer than V vertices are processed, at least one set of vertices still has incoming edges and cannot be released. That proves a cycle exists, although the remaining set may include nodes merely downstream of the actual cycle. Keep the residual nodes or predecessor information if callers need a precise diagnostic.

The queue policy is also part of the API. A FIFO queue gives one valid order, but it does not by itself guarantee a stable result when the input adjacency order changes. A sorted queue or priority queue gives deterministic tie-breaking, at an additional cost that should be stated.

Decision rule: Use Kahn's algorithm deliberately when indegrees and the set of currently available work make the contract or invariant easy to inspect. If it only reduces typing while hiding an assumption, prefer the more explicit design.

3. DFS topological order

DFS reaches as far as possible along a dependency chain before placing a vertex in the result. A vertex is appended on postorder, after all of its outgoing neighbors have been visited; reversing the finish order puts each prerequisite before the vertex that depends on it. This works only if DFS detects cycles while it runs.

Use three states, for example unvisited, visiting, and completed. Encountering an edge to a visiting vertex is a back edge and proves a directed cycle. An edge to a completed vertex is not a cycle by itself; this distinction is where implementations that use only a visited boolean commonly fail. An iterative DFS can avoid call-stack limits, while recursive DFS is often shorter but must account for graph depth.

Postorder/reverse-finish ordering gives a topological order if DFS detects no back edge or cycle. Recursion-stack state or colors are required for cycle detection.

Decision rule: Use DFS topological order deliberately when traversal state, postorder, or an existing DFS-based graph pipeline makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design.

4. Non-uniqueness

A topological sort does not usually answer “what is the one correct order?” It answers “give me an order satisfying all precedence constraints.” For a graph with independent vertices A and B, both A, B and B, A are valid. During Kahn's algorithm, multiple zero-indegree choices reveal this freedom directly. During DFS, adjacency traversal order can produce different valid results.

If a build, UI, or test suite needs repeatable output, make that a requirement and define the tie-breaker, such as lexical order, creation time, or an explicit priority. Do not confuse deterministic output with a stronger dependency relationship: choosing A before B does not mean the graph required that relationship.

A DAG can have many valid topological orders. If the queue has multiple zero-indegree choices, the ordering is not uniquely determined without an additional tie-breaking requirement.

Decision rule: Treat non-uniqueness deliberately when it affects reproducibility, caching, snapshots, or user-visible behavior. If an arbitrary choice only reduces typing while hiding an assumption, document or encode the tie-breaker instead.

5. Strongly connected components

Topological sorting cannot make a directed cycle disappear. When dependencies contain A -> B -> C -> A, those vertices are mutually reachable and form one strongly connected component, or SCC. SCC algorithms such as Kosaraju's or Tarjan's identify these maximal mutually reachable groups. Condensing each SCC into one vertex produces a component graph, and that graph is a DAG.

This gives dependency tooling two useful options. It can reject a nontrivial SCC as a cycle and report its members, or it can treat the component as a unit and topologically order the components around it. A single vertex with a self-loop is also cyclic, so do not assume that an SCC is valid merely because it contains one vertex.

In a directed graph, vertices are strongly connected when each can reach the other. SCC algorithms condense cycles into a DAG of components.

Decision rule: Use strongly connected components deliberately when cycle structure matters, such as diagnosing circular imports or grouping mutually dependent jobs. If it only reduces typing while hiding an assumption, retain the original graph and make the desired cycle policy explicit.

6. Dependency diagnosis

A topological failure should surface the cycle or affected nodes, not merely return an empty order. In practice, return a structured error containing at least the unprocessed vertices, and preferably a cycle witness or the SCCs that explain the failure. Distinguish the actual cycle from downstream vertices that could not be processed because the cycle blocked them.

This distinction matters operationally. A build service that says “dependency error” forces a developer to reconstruct the graph. A service that reports payments -> ledger -> payments, along with the configuration or source locations that created those edges, points directly to the repair. Production dependency tools need diagnostics that are stable enough for logs, metrics, and automation, while still avoiding sensitive input in user-visible output.

Decision rule: Use dependency diagnosis deliberately when a failed invariant needs to be repaired by a person or another system. If it only reduces typing while hiding an assumption, return the evidence needed to inspect the graph rather than an opaque failure.

Worked example

Consider both an interview-sized problem and a production data-processing problem. In either case, begin by writing the requirement in one sentence, listing the input and output contracts, and assigning each failure mode to the concept that owns it. For a dependency order, the input contract should say how vertices and directed edges are represented, whether missing vertices are allowed, and whether duplicate edges are meaningful. The output contract should say whether any valid order is acceptable, whether it must be deterministic, and how cycles are reported.

The important design move is separation. Parsing and boundary validation belong at the boundary. Domain rules belong in the domain or service layer. Persistence rules belong in the database or repository. Presentation rules belong in the client. Mixing these concerns can make a happy-path demo look shorter, but it makes duplicate edges, retries, malformed input, and dependency failures much harder to reason about.

The following small function is intentionally not a topological-sort implementation. It demonstrates the same habit of stating an invariant before choosing the data structure and loop. In a graph implementation, that invariant would describe indegrees, traversal state, or the ordering constraint.

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For this specific function, an empty list returns 0, which is only correct if the contract defines 0 as the empty-case result; otherwise the implementation needs a different return type or validation rule. For a topological sorter, ask the same question about an empty graph, an unknown endpoint, a duplicate edge, and a cycle. For each case, state which layer detects the problem and what the caller observes. That is the level of explanation expected in a senior code review or technical interview.

Production perspective

Production correctness is broader than “the code works on my machine.” Dependency graphs change during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high-cardinality workloads. Define what happens if one dependency is missing, if an edge is submitted twice, or if two workers try to process the same newly available vertex. Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Optimize only after evidence identifies the bottleneck or risk.

For a graph with V vertices and E edges, adjacency-list implementations of Kahn's algorithm and DFS topological ordering use O(V + E) time. They also use O(V + E) storage for the graph and O(V) additional algorithm state, excluding the output order. A priority queue preserves deterministic choices but changes the queue operations and commonly results in O((V + E) log V) time. SCC algorithms are typically O(V + E) as well. State these costs alongside practical limits such as recursion depth, memory required to retain diagnostics, and the cost of sorting input.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and the network input is untrusted. A graph supplied over the network must be validated and bounded; never let an untrusted request create unbounded memory or diagnostic output.

Guided lab

Implement Kahn's topological sort with deterministic tie-breaking and cycle detection. Return or report enough residual information to identify why a cycle blocked processing. Then study and implement Kosaraju's or Tarjan's SCC algorithm, and condense a cyclic dependency graph into a component DAG. Verify the component graph's acyclicity before applying a topological order to it.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing. Print or log indegrees, traversal states, or SCC membership in a controlled test environment.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it. For example, compare Kahn's algorithm with DFS and explain your cycle-reporting or determinism choice.
Record a short “what would break at 10× scale?” note. Include graph memory, recursion depth, queue behavior, and diagnostic volume where relevant.

Edge cases and failure modes

DAG: Test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include an empty graph, isolated vertices, a self-loop, and a graph whose edges form a long chain.
Kahn algorithm: Test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify that every emitted vertex had zero remaining indegree and that fewer than V processed vertices produces a cycle diagnosis.
DFS topological order: Test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include a back edge, a cross edge to a completed vertex, disconnected components, and a chain deep enough to expose recursion limits.
Non-uniqueness: Test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify both that multiple valid outputs are accepted when allowed and that the chosen tie-breaker is stable when determinism is required.
Strongly connected components: Test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include a self-loop, several disconnected SCCs, nested-looking but distinct cycles, and edges between components.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values.
Treating a topological order as unique when the graph has independent choices.
Marking a DFS vertex simply as “visited,” which loses the distinction between a back edge to the current path and an edge to a completed vertex.
Forgetting to initialize indegrees for isolated vertices, or counting duplicate edges inconsistently between adjacency and indegree structures.
Testing only the happy path and therefore discovering contracts only after integration.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees.

For debugging, reproduce the smallest failing case, inspect the actual graph and execution state, and trace the boundary where the invariant first becomes false. In Kahn's algorithm, inspect the vertices left with nonzero indegree. In DFS, inspect the current recursion path when a visiting vertex is encountered. For SCC analysis, inspect component membership and the condensed edges. Then fix the owning layer rather than adding a downstream patch.

Interview questions

What problem does a DAG solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Kahn's algorithm solve, and what trade-off or failure mode would make you choose a different approach?
What problem does DFS topological order solve, and what trade-off or failure mode would make you choose a different approach?
What problem does non-uniqueness solve, and what trade-off or failure mode would make you choose a different approach?
What problem do strongly connected components solve, and what trade-off or failure mode would make you choose a different approach?

Checkpoint

Without notes, explain Topological Sorting, DAGs, Dependencies, and Strongly Connected Components to another developer in five minutes. Your explanation must include the ordering invariant, one edge case, one production failure mode, and one alternative design. Explain why a cycle prevents a complete topological order and how SCC condensation can turn the larger dependency structure into a DAG. Then implement a small example without copying the lesson code.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.