Connected ComponentsWhat are Connected Components of a Graph?An undirected graph is called connected if for every pair of nodesu and v there is a path between u
and v. The connected components of an undirected graph
are its maximal connected subgraphs.
What are Connected Components good for?The decomposition of a graph into its components often allows to divide graph problems on undirected graphs into smaller subproblems, one for each components. Example of how to compute 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: |