# Connected Components

Vertices are said to be connected if there is a path between them. We would like to be able to answer the question "Is $v$ connected to $w$?" for any given graph.

To this end, If we view "is connected to" as a relation, we quickly see that it is an equivalence relation, as for any vertices $u$, $v$, and $w$, we know:

• $v$ is connected to $v$ -- so the reflexive property holds
• If $v$ is connected to $w$, then $w$ is connected to $v$ -- so the symmetric property holds.
• If $u$ is connected to $v$ and $v$ is connected to $w$, then $u$ is connected to $w$ -- so the transitive property holds.

With this, for a given graph and vertex, we can find a maximal set of connected vertices that includes the given vertex. Such a set is called a connected component. As an example, the connected component in the graph below that contains vertex 9 is shown below in blue (and given an "id" of 2).

By pre-processing a graph to identify the connected components to which each vertex belongs, we can answer queries of the form "Is $v$ connected to $w$?" in constant time!

This can be done using a depth-first search, as shown in the code that follows:

public class ConnectedComponents {

private boolean visited[];
private int[] id;
private int numComponents;

public ConnectedComponents(Graph g) {
visited = new boolean[g.numVertices()];
id = new int[g.numVertices()];
for (int v = 0; v < g.numVertices(); v++) {
if (! visited[v]) {
dfs(g,v);
numComponents++;
}
}
}

private void dfs(Graph g, int v) {
visited[v] = true;
id[v] = numComponents;
for (int w : g.adj(v)) {
if (! visited[w]) {
dfs(g,w);
}
}
}

public int count() {
return numComponents;
}

public int id(int v) {
return id[v];
}

public static void main(String[] args) {
Graph g = new Graph(13);