Graph connectivity component

Disconnected graph with three connected components

A connected component of a graph is a set of vertices of a graph such that for any two vertices from this set there is a path from one to another, and there is no path from the vertex of this set to a vertex not from this set.

For oriented graphs, the concept of a strong connected component is defined.

Algorithm

To search for components of connectivity, you can use the search in width or search in depth. In this case, the elapsed time will be linear (relative to the number of vertices and edges).

See also

• Connected graph
• Completely disconnected graph
• Glossary of graph theory
• The component of strong connectivity in the digraph
• Percolation theory