How do you count the connected components of an undirected graph?
You keep a set of the nodes you have already visited, and every time you find a node that is not in the set you have found a new component.
def count_components(graph):
seen = set()
components = 0
for node in graph:
if node in seen:
continue
components += 1
# Mark everything that is joined to this node.
stack = [node]
seen.add(node)
while stack:
current = stack.pop()
for neighbour in graph[current]:
if neighbour not in seen:
seen.add(neighbour)
stack.append(neighbour)
return components
So how does it work? You go through the nodes one at a time. If the node has already been seen then it belongs to a component that you have already counted, so you skip it. If it has not been seen then it is the start of a new component, so you add one to the count and you mark everything that is joined to it.
the graph the components
A: B, C one, made of A, B and C
B: A two, made of D
C: A
D:
E:
And the marking is what stops the counting from being wrong. When you find a new component you have to mark all of it, so that when the outer loop reaches the other nodes in that component it knows to skip them.
And there is a detail worth knowing about. The set seen is what stops the search from going round a cycle. The node is added to the set before it goes on the stack, so it is marked before you look at its neighbours.
And the complexity is O of n plus m for the time, where n is the number of nodes and m is the number of edges, because every node is visited once and every edge is looked at once. And the space is O of n for the set and the stack.
So the rule to remember is this. Every node that is not in the seen set starts a new component.
The last question in this topic shows the version for a list of edges.