# 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 2 November 2020.

HTML page formatted Mon Nov 2 12:36:42 2020.

Cite this as:

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