NIST

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 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

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