Strongly Connected ComponentsWhat are Strongly Connected Components of a Graph?A directed graph is called strongly connected if for every pair of verticesu and v there is a path from u to v
and a path from v to u. The
strongly connected components of a directed graph are its maximal
strongly connected subgraphs.
What are Strongly Connected Components good for?Many algorithms for directed graphs begin with a decomposition of the graph into its strongly connected components. This often allows to divide the original problem into smaller subproblems, one for each components. Example of how to compute strongly connected components Running TimeThe running time is linear in the size of the graph (O(|V|+|E|)). |
See also:GraphWin for visualizing graphs and graph algorithms Manual Entries: |