# 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, Java, and Mathematica)

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 12 August 2019.

HTML page formatted Mon Aug 12 09:59:40 2019.

Cite this as:

Alen Lovrencic, "connected components", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 12 August 2019. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/connectedComponents.html