Discrete Mathsfor Engineers

7. Applications II

Depth-First Search becomes especially powerful when we move from traversal to global graph decomposition.

In this part, we study strongly connected components (SCCs) and show how DFS reveals large-scale structure in directed graphs.

7.1 Strongly Connected Components

In a directed graph, two vertices u and v are strongly connected if:

That is, each vertex can reach the other.

A strongly connected component is a maximal set of vertices that are pairwise strongly connected.

7.2 SCCs as a Higher-Level Structure

If we collapse each SCC into a single super-vertex, we obtain the condensation graph.

A fundamental fact is:

So SCC decomposition turns an arbitrary directed graph into an acyclic structure of components.

7.3 Why Finish Times Matter Again

In Part 6, finish times gave a topological-style order for DAGs. Here they guide us across SCCs.

If one SCC can reach another SCC, then DFS tends to finish the source component later.

7.4 The Transpose Graph

The transpose of a directed graph G = (V, E) is the graph G^T = (V, E^T) obtained by reversing every edge:

SCCs are preserved under transposition: the components remain the same, but the direction between components reverses.

7.5 Kosaraju’s Algorithm

Kosaraju’s algorithm computes SCCs using two DFS passes:

1. Run DFS on G and record finish times.
2. Build the transpose graph G^T.
3. Run DFS on G^T in decreasing order of finish times.
4. Each DFS tree in the second pass is one SCC.

7.6 Kosaraju — Pseudocode Sketch

KOSARAJU(G):

    run DFS(G)
    let vertices be ordered by decreasing finish time

    compute G^T

    mark all vertices WHITE

    for each vertex u in decreasing finish-time order:
        if color[u] == WHITE:
            DFS-VISIT(G^T, u)
            output the vertices reached in this DFS as one SCC

The second DFS pass groups vertices into strongly connected components.

7.7 Why Kosaraju Works

The first DFS pass identifies an order that respects the component-level structure.

After transposition, edges between SCCs are reversed. So when the second pass starts from the largest remaining finish time, DFS stays inside exactly one SCC before crossing to others.

7.8 Complexity

Kosaraju’s algorithm runs in linear time:

because:

• the first DFS is linear,
• building the transpose is linear,
• the second DFS is linear.

7.9 Advanced DFS-Based Structures

DFS is also the foundation for deeper graph algorithms and structures:

• Tarjan’s SCC algorithm — SCCs using one DFS pass
• Bridges and articulation points — in undirected graphs
• Biconnected components
• Low-link values — a key DFS structural invariant

7.10 Engineering Use Cases

SCC decomposition appears in many real systems:

• dependency cycle analysis
• package/module graph condensation
• compiler optimization passes
• workflow and service dependency analysis

In practice, SCCs help turn cyclic systems into a DAG of strongly connected blocks.

7.11 Mini Summary

• SCCs are maximal mutually reachable vertex sets.
• Collapsing SCCs produces a DAG.
• Kosaraju uses two DFS passes and graph transposition.
• DFS remains linear while extracting deep global structure.