Topological Sorting and Strongly Connected Components Using DFS

Directed Acyclic Graphs and Dependency Ordering

A Directed Acyclic Graph (DAG) is a directed graph, as introduced earlier in this series, that contains no cycles. DAGs naturally model dependency relationships: a build system's compilation order, a project's task prerequisites, or a course catalog's prerequisite chains all form DAGs, where an edge from u to v means u must happen before v.

The Topological Sort Problem

A Topological Sort of a DAG is a linear ordering of all its vertices such that for every edge (u, v), u appears before v in the ordering. This provides a valid sequence for performing all the tasks represented by the graph while respecting every dependency.

Example: getting dressed, with dependencies
socks → shoes
underwear → pants
pants → shoes
pants → belt

A valid topological sort:
underwear, socks, pants, shoes, belt

(multiple valid orderings often exist;
 this is just one of them)

The Algorithm: DFS Plus Reverse Finishing Time

Topological sorting has a remarkably elegant algorithm built directly on the depth-first search finishing times discussed earlier in this series.

TOPOLOGICAL-SORT(G):
  call DFS(G) to compute finishing times v.f for each vertex
  as each vertex is finished, insert it onto the front of a linked list
  return the linked list

Equivalently, this can be described as: run DFS, and output the vertices in decreasing order of their finishing time.

Why This Simple Approach Works

The correctness argument relies on a key property: for any edge (u, v) in a DAG, v must finish before u does. This follows directly from the DFS edge classification discussed earlier in this series: since the graph is acyclic, edge (u, v) cannot be a back edge (which would create a cycle), so it must be a tree, forward, or cross edge, and in every one of these cases, v's finishing time is guaranteed to be earlier than u's.

If (u, v) is a tree edge or forward edge:
  v is a descendant of u, so v must finish before u
  (DFS-VISIT for u does not finish until all
   recursive calls, including the one for v, return)

If (u, v) is a cross edge:
  v must have already been completely finished
  before u's DFS-VISIT even discovered u,
  since v's subtree was fully explored first

Since v.f < u.f holds for every edge (u, v), sorting vertices by decreasing finishing time guarantees u appears before v for every edge, exactly satisfying the topological sort requirement.

Since this algorithm is simply DFS with one constant-time addition per vertex (prepending to a list), it runs in Θ(V + E) time, matching the efficiency of DFS itself.

Strongly Connected Components

In a directed graph, a Strongly Connected Component (SCC) is a maximal set of vertices such that every vertex in the set can reach every other vertex in the set via a directed path. This concept has no equivalent complexity in undirected graphs, where simple connectivity already captures this notion; in directed graphs, mutual reachability is a genuinely distinct and more restrictive property.

Example directed graph with SCCs:
a → b → c → a   (mutually reachable: one SCC {a, b, c})
c → d           (d is reachable from the first SCC)
d → e → d       (mutually reachable: another SCC {d, e})

This graph has 2 strongly connected components:
{a, b, c} and {d, e}

Kosaraju's Algorithm: An Elegant Two-Pass DFS Solution

Finding SCCs efficiently relies on a beautifully simple algorithm using exactly two passes of depth-first search, along with the graph's Transpose — the same graph with every edge direction reversed.

STRONGLY-CONNECTED-COMPONENTS(G):
  1. Call DFS(G) to compute finishing times u.f for each vertex u
  2. Compute Gᵀ (the transpose of G — reverse every edge)
  3. Call DFS(Gᵀ), but in the main loop, process vertices
     in order of DECREASING u.f (from step 1)
  4. Output the vertices of each tree in the resulting
     DFS forest (from step 3) as a separate SCC

Computing the transpose graph takes Θ(V + E) time using an adjacency list (discussed earlier in this series), by simply reversing each edge while building the new representation. Since the algorithm performs a constant number of DFS calls, each taking Θ(V + E) time, plus the transpose computation, the total running time is Θ(V + E).

The Intuition Behind Why This Works

This algorithm's correctness relies on a subtle but powerful property: the vertex with the highest finishing time from the first DFS pass must belong to a "source" SCC in the condensed component graph (the graph formed by shrinking each SCC into a single node) — meaning no other SCC has an edge into it. Running DFS on the transposed graph, starting from vertices with the highest finishing times, ensures each DFS-VISIT call in the second pass explores exactly one complete SCC before getting "stuck," since the reversed edges prevent the search from escaping into vertices belonging to a different SCC that has already been fully processed.

Why These Algorithms Matter in Practice

Topological sorting underlies task schedulers, build systems (determining compilation order based on file dependencies), and spreadsheet formula evaluation (computing cells in an order that respects which cells depend on others). Strongly connected components are used in compiler design (identifying mutually recursive function groups), analyzing web link structures, and detecting circular dependencies in software packages, where an SCC containing more than one vertex directly signals a problematic dependency cycle. Both algorithms exemplify a recurring theme in this series: the rich structural information captured by DFS's discovery and finishing times, first introduced earlier in this series, provides the foundation for solving problems that appear, at first glance, to have little to do with simple graph traversal.