A strongly connected component (SCC) of a directed graph is a maximal set of vertices such that every vertex in the set can be reached from every other vertex by following directed edges. Strongly connected components divide a graph into nonoverlapping regions of mutual reachability. Contracting each component to a single vertex produces a directed acyclic graph, separating the graph’s internal cyclic structure from the one-way connections between its components.
Definition
Let be a directed graph. Write when there is a directed path from vertex to vertex . Paths of length zero are allowed, so every vertex reaches itself.
Define a relation on by
This is an equivalence relation:
- Reflexivity: each vertex reaches itself.
- Symmetry: mutual reachability is symmetric by definition.
- Transitivity: if and are mutually reachable, and and are mutually reachable, concatenating paths establishes mutual reachability between and .
The strongly connected components are the equivalence classes of this relation. They therefore form a unique partition of the vertex set.
Equivalently, an SCC is a nonempty set whose induced subgraph is strongly connected and which is maximal under inclusion with that property. Maximal does not mean largest: a graph may contain many SCCs of different sizes, none of which can be enlarged while remaining strongly connected.
Although reachability is initially defined using paths in the entire graph, paths between vertices of one component cannot leave that component and later return. Any intermediate vertex on such a path is mutually reachable with the endpoints and therefore belongs to the same component.
The usual algorithmic setting assumes a finite graph. The equivalence-relation definition also applies to infinite directed graphs.
Examples and basic properties
Consider a graph with vertices and edges
Its SCCs are
The first three vertices form a directed cycle, as do the last two. The edge allows travel from the first component to the second, but no path returns. Consequently, the two sets do not combine into a single component.
Several consequences follow directly from the definition:
- Every vertex belongs to exactly one SCC.
- A singleton vertex is an SCC if it is not mutually reachable with any other vertex, whether or not it has a self-loop.
- A nonempty graph is strongly connected precisely when it has one SCC.
- Every directed cycle lies entirely within one SCC.
- Every SCC containing at least two vertices contains a directed cycle.
- Reversing every edge preserves the SCC partition, because it reverses reachability in both directions.
Strong connectivity does not require a direct edge between every pair of vertices. It also does not require a single simple directed cycle passing through every vertex: several cycles may overlap at shared vertices and together form one SCC.
Strong connectivity differs from weak connectivity, which ignores edge directions. A weakly connected directed graph can contain many SCCs. In an undirected graph, or a directed graph obtained by replacing every undirected edge with edges in both directions, strong components coincide with ordinary connected components.
Condensation graph
The condensation graph of has one vertex for each SCC. It contains an edge , for distinct components and , whenever the original graph contains an edge from a vertex of to a vertex of . Internal edges are omitted, and duplicate edges are usually merged.
The condensation graph is always acyclic. If distinct components lay on a directed cycle, every vertex in each of those components could reach every vertex in all the others. They would therefore be one component, contradicting their distinctness.
Condensation preserves reachability between components: a path from component to component exists in the condensation exactly when a vertex of can reach a vertex of in the original graph. Reachability consequently defines a partial order on the components.
A topological ordering of the condensation arranges the components so that every edge between components points forward. This supports computations that process dependencies component by component while treating cyclic dependencies within a component separately.
A component with no outgoing edge to another component is called a sink component; one with no incoming edge from another component is a source component. Every nonempty finite directed graph has at least one of each.
Algorithms
Several algorithms compute all SCCs in
time using adjacency-list representations. In asymptotic notation, this is linear in the graph’s representation size. The classical methods use depth-first search (DFS).
Kosaraju–Sharir algorithm
The Kosaraju–Sharir algorithm uses two DFS passes:
- Run DFS over the original graph, recording vertices in order of completion.
- Reverse every edge to obtain the transpose graph.
- Run DFS over the transpose, considering starting vertices in decreasing order of their completion times from the first pass.
Each DFS tree in the second pass gives one SCC. Vertices already visited in that pass are skipped.
The ordering ensures that each search enters an unvisited component from which it cannot escape into another unvisited component in the transpose. With this orientation of the two passes, components are discovered in a topological order of the original condensation graph. An equivalent variant performs the first pass on the transpose and the second on the original graph.
The algorithm is conceptually simple, but requires access to incoming as well as outgoing adjacency, or construction of the transpose.
Tarjan’s algorithm
Tarjan’s SCC algorithm, published in 1972, uses one DFS traversal and a stack of vertices whose components have not yet been completed.
Each vertex receives:
- a discovery index ;
- a low-link value ;
- a marker indicating whether it remains on the stack.
Initially,
When processing an edge :
If is unvisited, recursively visit it and update
Otherwise, if is still on the stack, update
If has already been assigned to a completed component, the edge does not affect the low-link value.
After all outgoing edges of have been processed, the condition
identifies the root of an SCC. Vertices are popped from the stack through , inclusive, and assigned to that component.
The stack-membership test is essential: reaching a vertex in an already completed SCC does not establish mutual reachability. Tarjan’s algorithm emits components in reverse topological order of the condensation.
Practical considerations
Both algorithms use auxiliary space beyond graph storage, though constructing a transpose may require an additional representation. Recursive DFS can exhaust a programming language’s call stack on deep graphs; explicit-stack implementations avoid that limitation.
The linear-time bound depends on representation. Scanning an adjacency matrix generally takes time, even for a sparse graph.
For testing whether a nonempty graph is strongly connected, a simpler method suffices: choose a vertex, check that it reaches every vertex, then repeat from the same vertex with all edges reversed. Both checks succeed exactly when the graph is strongly connected.
Applications
Dependency analysis and formal verification
In software dependency graphs, SCCs identify groups of mutually dependent modules, functions, or variables. A nontrivial component indicates a cyclic dependency, but does not by itself establish an error. The condensation organizes these groups into an acyclic dependency structure.
In formal verification, reachable SCCs help analyze recurring behavior in finite-state systems. A component containing a directed cycle can support an infinite execution that remains within it. Further conditions are needed when a specification requires particular accepting states, transitions, or fairness constraints.
Boolean satisfiability
SCC decomposition provides a linear-time method for 2-satisfiability (2-SAT). For a formula expressed as a conjunction of two-literal clauses, each clause
produces implication edges
The formula is satisfiable if and only if no variable and its negation belong to the same SCC of the resulting implication graph. A satisfying assignment, when one exists, can be constructed using an ordering of the components.
Markov chains
For a finite Markov chain, form a graph with an edge whenever the corresponding entry of the transition matrix is positive. Its SCCs are the chain’s communicating classes.
Sink components correspond to closed communicating classes: once the chain enters one, it cannot leave. In a finite chain, states in these closed classes are recurrent, whereas states outside them are transient. Strong connectivity of the entire transition graph is equivalent to irreducibility, but does not imply aperiodicity.
Matrix structure
Given a square matrix, construct a graph with an edge whenever the entry is nonzero. Ordering the SCCs topologically and applying the same permutation to rows and columns places the matrix in block upper-triangular form. The diagonal blocks correspond to SCCs.
This structural decomposition can expose independent or sequentially dependent parts of a system of linear equations, and is useful in sparse numerical computation.
Scope and limitations
Strongly connected components describe directed reachability, not distance, connection strength, or robustness. A component can be strongly connected while relying on a single crucial edge or vertex. Edge weights do not affect the decomposition unless they determine whether an edge exists.
SCCs also differ from statistical or community-based clusters. One-way edges may connect distinct SCCs very densely, while a large SCC may contain regions joined by only a few links.
The classical algorithms compute a static decomposition. Adding an edge can merge several components if it creates a return path between them; deleting an edge can split a component. Maintaining SCCs efficiently under repeated updates requires specialized dynamic algorithms.