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 E. Black.

Entry modified 18 October 2007.
HTML page formatted Tue Dec 6 16:16:32 2011.

Cite this as:
Alen Lovrencic, "connected components", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 18 October 2007. (accessed TODAY) Available from:

to NIST home page