The input is an undirected graph and a connected component is a maximal subgraph in where every two vertices in the subgraph are connected by a path of edges in the original graph. Maximal means that we make each component as large as possible.

Related Problems Edit


The matrix problem can be viewed as a special case of the connected components problem. To see this, look at the following example. On the left side we have a matrix as the input and on the right side we see the same input viewed as a graph.

Another related problem is to identify regions of the same colour in a matrix. Whether you have to count these regions, determine their areas or recolour them, the same basic algorithm can be used all the time.

Algorithm Edit

To Solve the general problem, we can use Depth First Search (DFS) to identify the connected components (CC) and when we apply this to all the nodes in the graph, we can detect all CCs.


int numberOfComponents ( Graph G ) {
    for each node N of G
        seen[N] = false;
    answer = 0
    for each node N of G
        if not seen[N]
            DFS( G, N )
    return answer

void DFS ( Graph G, Node N ) {
    if seen[N]
    seen[N] = true
    for each neighbour M of N in G
        DFS( G, M )

Here, a call of DFS(G,N) can mark all nodes in CC that N belongs to as "seen", so that we count each component exactly once. Note that this is a very simple use of DFS. It's probably one of the most versatile and useful algorithms out there.

See Also Edit