NIST

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, Pascal, Mathematica, and Fortran)

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 E. Black.

Entry modified 14 August 2008.
HTML page formatted Tue Dec 6 16:16:33 2011.

Cite this as:
Paul E. Black, "strongly connected component", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 August 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/stronglyConnectedCompo.html

to NIST home page