FANDOM


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

Connected-components

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.

pseudo-code

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]
            ++answer
            DFS( G, N )
    return answer
}

void DFS ( Graph G, Node N ) {
    if seen[N]
        return
    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

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.