# connected components

(definition)

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

**Generalization** (I am a kind of ...)

*partition*.

**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 G*_{1}=(V_{1}, E_{1})..., G_{m}=(V_{m}, E_{m}) 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, V_{i}∩ V_{j}=ø. Further, V=V_{1}∪...∪ V_{m} and E=E_{1}∪...∪ E_{m}.

Author: AL

## Implementation

(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: http://www.nist.gov/dads/HTML/connectedComponents.html