TOPICS
Search

Strongly Connected Component

A strongly connected component of a simple directed graph (i.e., a digraph without loops) is a maximal subdigraph such that for every pair of distinct vertices u, v in the subdigraph, there is a directed path from u to v.

Tarjan (1972) has devised an O(n) algorithm for determining strongly connected components, which is implemented in the Wolfram Language as ConnectedGraphComponents[g].

See also

Bi-Connected Component, Connected Component, Directed Graph, Strongly Connected Digraph, Weakly Connected Component

Explore with Wolfram|Alpha

References

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Tarjan, R. E. "Depth-First Search and Linear Graph Algorithms." SIAM J. Comput. 1, 146-160, 1972.

Referenced on Wolfram|Alpha

Strongly Connected Component

Cite this as:

Weisstein, Eric W. "Strongly Connected Component." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/StronglyConnectedComponent.html

Subject classifications