Strongly connected component

Strongly connected component

A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. The strongly connected components (SCC) of a directed graph are its maximal strongly connected subgraphs. If each strongly connected component is contracted to a single vertex, the resulting graph is a directed acyclic graph.

Kosaraju's algorithm, Tarjan's algorithm and Gabow's algorithm all efficiently compute the strongly connected components of a directed graph, but Tarjan's and Gabow's are favoured in practice since they require only one depth-first search rather than two.

See also


Search another word or see strongly connected componenton Dictionary | Thesaurus |Spanish
Copyright © 2015, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature