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); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(0, 5); g.addEdge(0, 6); g.addEdge(3, 4); g.addEdge(3, 5); g.addEdge(4, 5); g.addEdge(4, 6); g.addEdge(7, 8); g.addEdge(9, 10); g.addEdge(9, 11); g.addEdge(9, 12); g.addEdge(11, 12); ConnectedComponents cc = new ConnectedComponents(g); System.out.println(" v | id[v]"); System.out.println("-----|------"); for (int v = 0; v < g.numVertices(); v++) { System.out.println((v < 10 ? " " : " ") + v + " " + " | " + cc.id(v)); } } }