(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
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.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 2 September 2014.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
Paul E. Black, "strongly connected component", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 September 2014. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/stronglyConnectedCompo.html