From Reachability to Components
To find the connected components of a graph, it is not enough to list the neighbors of one vertex: a vertex can be reachable by a path that uses several edges. A systematic search keeps track of which vertices have already been found and continues exploring until no new vertex can be added. Repeating the search from an unassigned vertex then finds the next component.
All graphs in this tutorial are finite and simple. A path from \(u\) to \(v\) is a sequence of distinct vertices starting at \(u\) and ending at \(v\), with consecutive vertices joined by an edge. A vertex is reachable from \(u\) if there is such a path from \(u\) to that vertex; \(u\) itself is reachable by the path consisting of \(u\) alone.
An adjacency list records, for each vertex, all vertices adjacent to it. Since the graphs here are undirected, if \(v\) occurs in the list for \(u\), then \(u\) occurs in the list for \(v\). During the search, a queue stores discovered vertices that have not yet had their adjacency lists examined. A vertex is marked as discovered as soon as it is put in the queue, so it cannot be added repeatedly.
A Systematic Search
Choose a vertex \(r\) not yet assigned to a component. Mark \(r\) discovered and place it in the queue.
Remove the first vertex \(u\) from the queue and inspect every neighbor of \(u\).
For each neighbor not yet discovered, mark it discovered and add it to the end of the queue. Neighbors already discovered are not added again.
Continue until the queue is empty. The discovered vertices form the component containing \(r\).
If any vertex remains unassigned, choose one as the next seed and repeat. Stop when every vertex has been assigned.
The search depends on which vertices are adjacent, not on the order in which neighbors are examined. Choosing a consistent order, such as alphabetical order or increasing numerical order, makes a trace easier to check. The queue is a bookkeeping device: this tutorial uses it to find reachability, not to calculate distances.
Proof. First, every discovered vertex is reachable from \(r\). This holds initially because \(r\) is reachable from itself. Whenever a vertex \(u\) is processed, a newly discovered vertex \(v\) is adjacent to \(u\). If \(u\) is reachable from \(r\), adjoining the edge \(uv\) gives a walk from \(r\) to \(v\), and removing any repeated portions of that walk gives a path from \(r\) to \(v\). Thus every vertex added during the search is reachable. Conversely, let \(v\) be reachable from \(r\), and choose a path \(r=v_0,v_1,\ldots,v_k=v\). The vertex \(v_0=r\) is discovered initially. Whenever \(v_i\) is discovered, it is eventually processed: the graph is finite, and each discovered vertex is placed in the queue only once. When \(v_i\) is processed, its neighbor \(v_{i+1}\) is either already discovered or is discovered then. Inducting along the path shows that \(v\) is discovered. Therefore the search discovers all and only the vertices reachable from \(r\). \(\square\)
Proof. If the vertex set is empty, there is no possible seed and the procedure returns no sets, as required. Otherwise, consider a search started at a seed \(r\). By the preceding theorem, its discovered set consists exactly of the vertices reachable from \(r\). These vertices form a connected set: for any two of them, a path from each to \(r\) gives a walk between them, from which a path can be obtained by deleting repeated portions. The set is maximal among connected sets containing \(r\), because a vertex that could be added while preserving connectedness would be reachable from \(r\), and so would already have been discovered. After the search ends, no vertex in its set is left unassigned. A later seed therefore cannot be in that set, and the same reasoning gives a different component. Each search assigns at least its seed, so the process terminates after finitely many searches. Every vertex is assigned when the process stops. Hence the output consists of all components, each exactly once. If a seed has no neighbors, its search discovers just that vertex, giving its singleton component. \(\square\)
Worked Searches
Worked Example: Three Components, Including an Isolated Vertex
Let \(G=(V,E)\), where \(V=\{1,2,3,4,5,6,7,8\}\) and \(E=\{12,13,24,34,45,67\}\). The adjacency lists are \(1:\{2,3\}\), \(2:\{1,4\}\), \(3:\{1,4\}\), \(4:\{2,3,5\}\), \(5:\{4\}\), \(6:\{7\}\), \(7:\{6\}\), and \(8:\varnothing\). Begin with seed \(1\); examine neighbors in increasing order. The discovered set includes vertices already processed as well as those still in the queue.
| Vertex processed | New vertices discovered | Queue afterward | Discovered set afterward |
|---|---|---|---|
| Initial state | \(1\) | \([1]\) | \(\{1\}\) |
| \(1\) | \(2,3\) | \([2,3]\) | \(\{1,2,3\}\) |
| \(2\) | \(4\) | \([3,4]\) | \(\{1,2,3,4\}\) |
| \(3\) | None; \(1,4\) are discovered | \([4]\) | \(\{1,2,3,4\}\) |
| \(4\) | \(5\) | \([5]\) | \(\{1,2,3,4,5\}\) |
| \(5\) | None; \(4\) is discovered | \([]\) | \(\{1,2,3,4,5\}\) |
The first search gives \(\{1,2,3,4,5\}\). To check reachability directly, paths from \(1\) to the other vertices in this set are \(1,2\) to \(2\); \(1,3\) to \(3\); \(1,2,4\) to \(4\); and \(1,2,4,5\) to \(5\). Each consecutive pair in each sequence is an edge in \(E\). Vertices \(6,7,8\) have not been assigned, so restart at \(6\). The initial queue is \([6]\), and processing \(6\) discovers \(7\), leaving queue \([7]\) and discovered set \(\{6,7\}\). Processing \(7\) adds no new vertex, leaving the queue empty. The next unassigned vertex, \(8\), has no neighbors: its search starts with queue \([8]\), processes \(8\), and ends with queue \([]\).
The components are therefore \(\{1,2,3,4,5\}\), \(\{6,7\}\), and \(\{8\}\). As a check, these sets are disjoint and their union is \(V\). Each listed edge has both endpoints in one of the sets: \(12,13,24,34,45\) are within the first, \(67\) is within the second, and there is no edge incident with \(8\).
Worked Example: Finding Components from an Edge Set
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e,f,g\}\) and \(E=\{ab,bc,ca,cd,ef\}\). Its adjacency lists are \(a:\{b,c\}\), \(b:\{a,c\}\), \(c:\{a,b,d\}\), \(d:\{c\}\), \(e:\{f\}\), \(f:\{e\}\), and \(g:\varnothing\). Start at \(a\) and examine neighbors alphabetically.
| Vertex processed | New vertices discovered | Queue afterward | Discovered set afterward |
|---|---|---|---|
| Initial state | \(a\) | \([a]\) | \(\{a\}\) |
| \(a\) | \(b,c\) | \([b,c]\) | \(\{a,b,c\}\) |
| \(b\) | None; \(a,c\) are discovered | \([c]\) | \(\{a,b,c\}\) |
| \(c\) | \(d\) | \([d]\) | \(\{a,b,c,d\}\) |
| \(d\) | None; \(c\) is discovered | \([]\) | \(\{a,b,c,d\}\) |
The first component is \(\{a,b,c,d\}\). Paths from the seed \(a\) are \(a,b\) to \(b\), \(a,c\) to \(c\), and \(a,c,d\) to \(d\). Restarting at \(e\) gives queue \([e]\); processing \(e\) discovers \(f\) and leaves queue \([f]\). Processing \(f\) adds nothing, so the next component is \(\{e,f\}\). Finally, \(g\) is unassigned and has an empty adjacency list. Starting with \([g]\) and processing \(g\) leaves the queue empty, giving component \(\{g\}\).
Check: The three sets are disjoint and together contain all seven vertices. The edges \(ab,bc,ca,cd\) lie within \(\{a,b,c,d\}\), the edge \(ef\) lies within \(\{e,f\}\), and no edge joins these sets to each other or to \(\{g\}\). Thus none of the searches has missed a connection to another listed component.
Worked Example: Starting in the Middle of a Component
Let \(G=(V,E)\), where \(V=\{p,q,r,s,t,u,v\}\) and \(E=\{pq,qr,rs,st,tu\}\). The adjacency lists are \(p:\{q\}\), \(q:\{p,r\}\), \(r:\{q,s\}\), \(s:\{r,t\}\), \(t:\{s,u\}\), \(u:\{t\}\), and \(v:\varnothing\). Start at \(s\), rather than at an endpoint.
| Vertex processed | New vertices discovered | Queue afterward | Discovered set afterward |
|---|---|---|---|
| Initial state | \(s\) | \([s]\) | \(\{s\}\) |
| \(s\) | \(r,t\) | \([r,t]\) | \(\{r,s,t\}\) |
| \(r\) | \(q\) | \([t,q]\) | \(\{q,r,s,t\}\) |
| \(t\) | \(u\) | \([q,u]\) | \(\{q,r,s,t,u\}\) |
| \(q\) | \(p\) | \([u,p]\) | \(\{p,q,r,s,t,u\}\) |
| \(u\) | None; \(t\) is discovered | \([p]\) | \(\{p,q,r,s,t,u\}\) |
| \(p\) | None; \(q\) is discovered | \([]\) | \(\{p,q,r,s,t,u\}\) |
The component containing \(s\) is \(\{p,q,r,s,t,u\}\). Paths from \(s\) to the other vertices are \(s,r\) to \(r\); \(s,r,q\) to \(q\); \(s,r,q,p\) to \(p\); \(s,t\) to \(t\); and \(s,t,u\) to \(u\). The only remaining vertex is \(v\). Its adjacency list is empty, so starting at \(v\) gives the singleton component \(\{v\}\).
Check: The edges \(pq,qr,rs,st,tu\) all have both endpoints in \(\{p,q,r,s,t,u\}\). No edge is incident with \(v\). Starting in the middle changes the order of discovery, but it does not change which vertices are reachable from \(s\).
Why the Search Must Continue
A frequent mistake is to stop after examining only the seed’s immediate neighbors. In the first example, the neighbors of \(1\) are just \(\{2,3\}\). Calling \(\{1,2,3\}\) the component would be wrong: the edge \(24\) makes \(4\) reachable from \(1\), and \(45\) then makes \(5\) reachable. The queue corrects this calculation by examining the newly discovered vertices as well as the seed. The search is finished only when every discovered vertex has been processed and the queue is empty.
It is also important to distinguish “discovered” from “not yet processed.” A discovered vertex belongs to the current component even if it is still waiting in the queue. Marking vertices when they are enqueued prevents repeated additions when, for example, two already discovered vertices share a neighbor. Conversely, an isolated vertex must not be discarded: its search has one seed, processes it, and ends with the singleton component containing that vertex.
Component searches are useful whenever a graph represents a system whose connections determine which objects can communicate or interact. They separate the graph into independent connected parts and provide a direct check of the component partition: every vertex must occur in exactly one part, and no edge may join two different parts. The edge check is a useful final safeguard, but the search is what ensures that each part contains every vertex reachable within it.
Check Your Understanding
For each question, use the adjacency lists or edge sets to justify the reachability claims.
- Let \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,45\}\). Starting at \(2\), what vertices are discovered? What are all the components?
- Explain why a vertex is marked discovered when it is added to the queue rather than when it is removed from the queue.
- Give the queue trace for a search starting at \(b\) in the graph with \(V=\{a,b,c,d\}\) and \(E=\{ab,bc,cd\}\), examining neighbors alphabetically.
- What does the procedure return when \(V=\varnothing\)? What does it return for a graph with one vertex and no edges?
- In a completed component search, explain why there cannot be an edge from a discovered vertex to a vertex outside the discovered set.