# strongly connected component

(definition)

**Definition:**
A *strongly connected* *subgraph*, S, of a *directed graph*, D, such that no *vertex* of D can be added to S and it still be strongly connected. Informally, a maximal subgraph in which every vertex is *reachable* from every other vertex.

**Generalization** (I am a kind of ...)

*maximally connected component*, *strongly connected graph*, *connected graph*.

**Aggregate child** (... is a part of or used in me.)

*depth-first search*.

**See also**
*cycle*.

*Note:
If a graph is strongly connected, it has only one strongly connected component. *

*
* The strongly connected components *partition* the vertices in the graph. That is, every vertex is in exactly one strongly connected component.

* After Robert Caswell (caswer01@cs.uwa.edu.au), 3 May 2002.*

Author: PEB

## Implementation

(C++, C, Java, and Mathematica)
## More information

Transitive closure has a link to **Esko Nuutila** and **Eljas Soisalon-Soininen**, *On finding the strongly connected components in a directed graph* (PostScript®), Information Processing Letters 49 (1993) 9-14. The paper has Tarjan's algorithm, references to other algorithms, and two faster algorithms in Pascal-like pseudo-code.

This has a linear time algorithm for finding strongly connected components:

**Robert E. Tarjan**, *Depth-first search and linear graph algorithms*, SIAM Journal on Computing, 1(2):146-160, 1972.

Go to the
Dictionary of Algorithms and Data
Structures home page.

If you have suggestions, corrections, or comments, please get in touch
with Paul Black.

Entry modified 2 November 2020.

HTML page formatted Mon Nov 2 12:36:42 2020.

Cite this as:

Paul E. Black, "strongly connected component", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 2 November 2020. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/stronglyConnectedCompo.html