How do you count the connected components of an undirected graph?
Keep a set of visited nodes. For each node in the graph, if it has not been visited then it starts a new component, so increment the counter and run a full search from it, marking everything reachable as visited.
def count_components(graph):
seen = set()
components = 0
for node in graph:
if node in seen:
continue
components += 1
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
graph = {"A": ["B"], "B": ["A"], "C": ["D"], "D": ["C"], "E": []}
print(count_components(graph))The output is 3. A and B form one component, C and D form a second, and E is isolated, so it is a component of its own.
The mechanism is that the inner search visits exactly the component that the starting node belongs to. Once it finishes, every node in that component is marked, so the outer loop will skip all of them. The outer loop therefore increments the counter exactly once per component, and the total work is linear in the number of nodes and edges because each node is visited once.
The trade-off to name is the memory for the visited set and the stack, both proportional to the size of the graph, and the recursion depth if you write the inner search recursively. A recursive version is shorter and is fine for most graphs, but a long chain of nodes can exceed the Python recursion limit, which is why the version above uses an explicit stack. The other point is that this assumes the adjacency list is symmetric for an undirected graph, since the traversal follows the neighbour lists in both directions. If the graph is given as an edge list, you have to add each edge in both directions first, which the next answer shows.