Depth-First Traversal and Connected Components
The main idea of Depth First Search is to first take an unvisited vertex as the starting vertex, and along the edges of the current vertex move to an unvisited vertex. When there is no unvisited vertex, return to the previous vertex and continue trying other vertices until all vertices have been visited.
The graph in the example below starts traversal from 0, and the order is shown in the right figure:
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, namely itself; a non-connected undirected graph has multiple connected components. There are no edges between connected components. Depth First Search can be used to find connected components.
The following uses finding connected components as an example to implement depth-first traversal of a graph, called dfs. In the code snippet below, the visited array records whether a node has been visited during dfs, ccount records the number of connected components, the id array represents the connected component label corresponding to each node, and two nodes having the same id value means they belong to the same connected component.
// Constructor, find the connected components of an unweighted 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 traversal of a graph is a recursive process; implementation code:
// Depth-first traversal 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 package download:Download
src/example/graph/Components.java file code:
import example.graph.read.Graph;
/**
* Depth-First Traversal
*/
public class Components {
Graph G; // Reference to the graph
private boolean[] visited; // Record whether a node is visited during DFS
private int ccount; // Record the number of connected components
private int[] id; // The connected component label corresponding to each node
// Depth-first traversal 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, find the connected components of an unweighted 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 ++;
}
}
// Return the number of connected components of the graph
int count(){
return ccount;
}
// Query whether node v and node 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];
}
}