Elijah's Notes

Finding Connected Components in Undirected Graphs Using BFS/DFS

2 min read

Purpose

Given an undirected graph , you can partition into connected components in using breadth-first search (BFS) or depth-first search (DFS). The payoff is a data structure built once from that answers whether a path exists between two vertices in time and space: two vertices are connected exactly when they carry the same component label.

Algorithm

Scan the vertices in order. Each time you hit a vertex that has no label yet, it starts a new component: run BFS (or DFS) from it and stamp every vertex you reach with the current label, then increment the label. Each traversal stays inside one component because BFS only follows edges, and it covers the whole component because BFS reaches everything connected to its source. Store the labels in an array (if vertices are numbered) or a hash map.

On the graph below the scan starts traversals at vertices 0, 3, and 5, and each traversal stamps one box:

flowchart LR
    subgraph C0["label 0"]
        n0((0)) --- n1((1))
        n1 --- n2((2))
        n2 --- n0
    end
    subgraph C1["label 1"]
        n3((3)) --- n4((4))
    end
    subgraph C2["label 2"]
        n5((5)) --- n6((6))
    end

from collections import deque, defaultdict
 
def connected_components(graph):
    a = [None] * len(graph)
 
    def bfs(label, src):
        q = deque([src])
        a[src] = label
        while q:
            curr = q.popleft()
            for v in graph[curr]:
                if a[v] is None:
                    a[v] = label
                    q.append(v)
 
    curr_label = 0
    for v in range(len(graph)):
        if a[v] is None:
            bfs(curr_label, v)
            curr_label += 1
    return a
 
def component_sets(G):
    comp = connected_components(G)
    component_dict = defaultdict(set)
    for v, c in enumerate(comp):
        component_dict[c].add(v)
    return list(component_dict.values())

The label array doubles as the visited set, so every vertex enters the queue at most once and the total work over all traversals is .

Undirected graphs only

The labeling argument relies on connectivity being symmetric. In a directed graph reachability is not symmetric, so this scan computes weakly connected components at best. Strongly connected components need Tarjan’s or Kosaraju’s algorithm.

Strategy for Unconnected Graphs

When solving a graph problem, first assume the graph is connected. Once you have a solution for connected graphs, run it separately on each connected component.

Graph View