Source code online books for professionals by professionals

Listing 5-2.  Finding Connected Components
def components(G):                              # The connected components
    comp = []
    seen = set()                                # Nodes we've already seen
    for u in G:                                 # Try every starting point
        if u in seen: continue                  # Seen? Ignore it
        C = walk(G, u)                          # Traverse component
        seen.update(C)                          # Add keys of C to seen
        comp.append(C)                          # Collect the components
    return comp
 
The walk function returns a predecessor map (traversal tree) for the nodes it has visited, and I collect those in the 
comp list (of connected components). I use the seen set to make sure I don’t traverse from a node in one of the earlier, 
already visited components. Note that even though the operation seen.update(C) is linear in the size of C, the call to 
walk has already done the same amount of work, so asymptotically, it doesn’t cost us anything. All in all, finding the 
components like this is Q(E +V) because every edge and node has to be explored.
4
The walk function doesn’t really do all that much. Still, in many ways, this simple piece of code is the backbone of 
this chapter and (as the chapter title says) a skeleton key to understanding many of the other algorithms you’re going 
to learn. It might be worth studying it a bit. Try to perform the algorithm manually on a graph of your choice (such 
as the one in Figure 
5-1
). Do you see how it is guaranteed to explore an entire connected component? It’s important 
4
This is the running time of all the traversal algorithms in this chapter, except (sometimes) IDDFS.

---

Chapter 5 
■
 traversal: the skeleton key of algorithmiCs
97
to note that the order in which the nodes are returned from Q.pop does not matter. The entire component will be 
explored, regardless. That very order, though, is the crucial element that defines the behavior of the walk, and by 
tweaking it, we can get several useful algorithms right out of the box.
For a couple of other graphs to traverse, see Figures 
5-3
 and 
5-4
. (For more about these examples, see the nearby 
sidebar.)
Figure 5-3.  The bridges of Königsberg (today, Kaliningrad) in 1759. The illustration is taken from Récréations 
Mathématiques, vol 1 (Lucas, 1891, p. 22)

---

Chapter 5 
■
 traversal: the skeleton key of algorithmiCs
98