Connected Components
Connected components algorithm receives an undirected graph 
as an input and searches for connected components in 
.
For each vertex in , the algorithm returns the label of the component this vertex belongs to.
The result of the algorithm is a set of labels for all vertices in .
as an input and searches for connected components in .
For each vertex in , the algorithm returns the label of the component this vertex belongs to.
The result of the algorithm is a set of labels for all vertices in .Operation | Computational methods | Programming Interface |
Mathematical formulation
Computing
Given an undirected graph , the problem is to find connected components in ,
determine their quantity, and label vertices so that vertices from the same component have the same label.
, the problem is to find connected components in ,
determine their quantity, and label vertices so that vertices from the same component have the same label.Example
Сomponents are labeled from 
to 
, where 
is the number of components.
For the example above, the labels for vertices are [0, 1, 1, 1, 2, 0, 1, 3, 4, 4, 4, 4, 4].
to , where is the number of components.
For the example above, the labels for vertices are [0, 1, 1, 1, 2, 0, 1, 3, 4, 4, 4, 4, 4].This notation means that:
- vertices with ids 0 and 5 belong to the connected component with id 0
- vertices with ids 1, 2, 3, and 6 belong to the connected component with id 1
- vertex with id 4 belongs to the connected component with id 2
- vertex with id 7 belongs to the connected component with id 3
- vertices with ids 8, 9, 10, 11, and 12 belong to the connected component with id 4
Computation method:
afforest
The method defines Afforest algorithm and solves the problem of сonnected components identification in an undirected graph.
This algorithm expands the Shiloach-Vishkin connected components algorithm and uses component approximation to decrease redundant edge processing. The method consists of the following steps:
- Process a fixed number of edges for each vertex (Vertex Neighbor Sampling optimization).
- Identify the largest intermediate component using probabilistic method.
- Process the rest of the neighborhoods only for the vertices that do not belong to the largest component (Large Component Skipping optimization).
For more details, see [Sutton2018].
Programming Interface
Refer to API Reference: Connected Components.