Depth-First Search and Connected Components

The main idea of Depth-First Search (DFS) is to start with an unvisited vertex as the initial vertex and traverse along the edges of the current vertex to an unvisited vertex. When there are no more unvisited vertices, it returns to the previous vertex and continues to explore other vertices until all vertices have been visited.

The example graph below starts traversal from vertex 0 as shown on the right:

A maximal connected subgraph of an undirected graph G is called a connected component (or connected branch) of G. A connected graph has only one connected component, which is itself; a disconnected undirected graph has multiple connected components. Connected components are not connected by any edges. Depth-First Search can be used to find connected components.

Below is an example of implementing DFS to find connected components, referred to as dfs. In the code snippet, the visited array records whether a node has been visited during the DFS process, ccount records the number of connected components, and the id array represents the connected component label for each node. Nodes with the same id value belong to the same connected component.

...
// Constructor, finds the connected components of an undirected graph
public Components(Graph graph){
    // Algorithm initialization
    G = graph;
    visited = new boolean[G.V()];
    id = new int[G.V()];
    ccount = 0;
    for( int i = 0 ; i < G.V() ; i ++ ){
        visited[i] = false;
        id[i] = -1;
    }
    // Find the connected components of the graph
    for( int i = 0 ; i < G.V() ; i ++ )
        if( !visited[i] ){
            dfs(i);
            ccount ++;
        }
}
...

Depth-First Search of a graph is a recursive process, implemented as follows:

...
// Depth-First Search of the graph
void dfs( int v ){
    visited[v] = true;
    id[v] = ccount;
    for( int i: G.adj(v) ){
        if( !visited[i] )
            dfs(i);
    }
}
...

Java Example Code

Source Code Download: Download

src/tutorialpro/graph/Components.java File Code:

package tutorialpro.graph;

import tutorialpro.graph.read.Graph;

/**
 * Depth-First Search
 */
public class Components {

    Graph G;                      // Reference to the graph
    private boolean[] visited;    // Records whether nodes have been visited during DFS
    private int ccount;           // Records the number of connected components
    private int[] id;             // Labels each node with its connected component

    // Depth-First Search of the graph
    void dfs( int v ){
        visited[v] = true;
        id[v] = ccount;
        for( int i: G.adj(v) ){
            if( !visited[i] )
                dfs(i);
        }
    }

    // Constructor, finds the connected components of an undirected graph
    public Components(Graph graph){
        // Algorithm initialization
        G = graph;
        visited = new boolean[G.V()];
        id = new int[G.V()];
        ccount = 0;
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            id[i] = -1;
        }
        // Find the connected components of the graph
        for( int i = 0 ; i < G.V() ; i ++ )
            if( !visited[i] ){
                dfs(i);
                ccount ++;
            }
    }
}

ccount++;
}
}

// Return the number of connected components in the graph
int count() {
    return ccount;
}

// Check if vertices v and w are connected
boolean isConnected(int v, int w) {
    assert v >= 0 && v < G.V();
    assert w >= 0 && w < G.V();
    return id[v] == id[w];
}