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