connected components


Definition: The set of maximally connected components of an undirected graph.

Generalization (I am a kind of ...)

See also connected graph, biconnected component, undirected graph, subgraph, clique, strongly connected components.

Note: If a graph is connected, it has only one connected component. Often the term "component" is used, with the "connected" property understood.

Let G=(V, E) be a graph and G1=(V1, E1)..., Gm=(Vm, Em) be its connected components. Every vertex is in exactly in one connected component, that is, the components partition(1) V. Formally, for all i ≠ j, Vi∩ Vj=ø. Further, V=V1∪...∪ Vm and E=E1∪...∪ Em.

Author: AL


(C++, C, Pascal, Mathematica, and Fortran)
Go to the Dictionary of Algorithms and Data Structures home page.

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:39 2015.

Cite this as:
Alen Lovrencic, "connected components", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 September 2014. (accessed TODAY) Available from: