Connected Components, in depth: DFS and BFS labelling, iterative traversal, union-find for streaming edges, weak components and parallel algorithms

Labelling with depth-first search

The algorithm is a sweep plus a search. Walk the vertices in any order. When you reach one without a label, it starts a new component: give it the next label and search outward, labelling everything reachable. Each vertex is labelled once and each edge examined twice (once from each end), so the total work is O(V + E) with an adjacency list. An adjacency matrix would make it O(V²), which is why sparse graphs should never be stored that way.

The recursive version is four lines long and a common production bug. CPython's default recursion limit is 1,000 frames, and a path graph or a long chain of linked records needs one frame per vertex. Raising the limit is fragile: safe depths differ between Python versions, platforms and threads. Use an explicit stack instead; the stack technique is covered generally in Iterative DFS with an explicit stack.

def components(n, edges):
    """Label vertices 0..n-1 of an undirected graph. Returns (labels, count)."""
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    label = [-1] * n
    count = 0
    for start in range(n):
        if label[start] != -1:
            continue
        label[start] = count            # label when pushed, not when popped
        stack = [start]
        while stack:
            u = stack.pop()
            for v in adj[u]:
                if label[v] == -1:
                    label[v] = count
                    stack.append(v)
        count += 1
    return label, count

Labelling a vertex when it is pushed, rather than when it is popped, is what keeps each vertex on the stack at most once. Label on pop and a dense vertex can be pushed once per neighbour, which inflates memory to O(E). Strictly, this loop visits vertices in a different order from recursive DFS, but for components the order does not matter: any complete search from the start vertex reaches exactly the same set.

Breadth-first search, grids and images

Swap the stack for a queue and you have breadth-first labelling: same labels, same complexity. BFS is the better choice when you want something besides membership, such as the hop distance from a seed, and its frontier is often smaller than a DFS stack on wide, shallow graphs. On grids, both specialise to flood fill, covered in Flood fill algorithms, where the neighbours of a pixel are computed on the fly and no adjacency list is stored at all. Image libraries label components with two-pass raster scans instead of searches, recording label equivalences in a union-find on the first pass, because a row-by-row scan is far friendlier to caches than jumping around an image.

On grids, decide connectivity explicitly. Four-connectivity treats only horizontal and vertical neighbours as adjacent; eight-connectivity adds diagonals. The same image can have very different component counts under the two rules: a diagonal line of pixels touching only at corners is one component under eight-connectivity and as many components as it has pixels under four. Pick the rule that matches the meaning of adjacency in your data, write it in the function signature, and test a diagonal case so nobody changes it by accident.

Worked example: ten vertices, four components

Take ten vertices and the edges 0-1, 1-2, 2-0, 3-4, 5-6, 6-7 and 7-8. Vertex 9 has no edges. The sweep starts at 0: it is unlabelled, so it gets label 0 and the search pushes 1 and 2, both labelled 0. Popping 2 finds neighbours 1 and 0, already labelled. Popping 1 finds the same. The stack empties: component 0 is {0, 1, 2}.

The sweep skips 1 and 2 and reaches 3, which starts component 1 and pulls in 4. Vertex 5 starts component 2; the search walks 6, 7 and 8 along the path. Vertices 6 to 8 are skipped by the sweep. Vertex 9 starts component 3 by itself: an isolated vertex is a component of size one, and forgetting it is the most common off-by-something in hand-rolled code. Four components, each vertex labelled once, each edge looked at twice.

Union-find when edges stream in

DFS needs the whole adjacency list in memory before it starts. When edges arrive one at a time, from a log, a join or a stream, union-find (disjoint-set union) is the better tool. Each vertex points to a parent; the root of its tree names its component. Union links two roots, find follows parents to the root. With union by size or rank and path compression, a sequence of m operations on n elements costs O(m α(n)), where α is the inverse Ackermann function, below 5 for any input that fits in the universe.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.count = n                       # components so far

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:        # path compression, iterative
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                 # attach smaller under larger
        self.size[ra] += self.size[rb]
        self.count -= 1
        return True

Union-find keeps O(n) memory regardless of edge count, answers same-component queries at any moment, and tracks the component count for free. What it cannot do cheaply is list the members of a component (you group by find afterwards) or undo a union. Variants and proofs are in Union-find in depth.

Directed graphs: weak versus strong

In a directed graph, connectivity splits into two notions. Weakly connected components ignore edge direction: treat every arc as undirected and run any method above. They answer questions like which services touch each other at all. Strongly connected components require a directed path both ways and answer questions like which modules form a dependency cycle; they need Tarjan's or Kosaraju's algorithm, covered in Tarjan's strongly connected components. Running undirected labelling on a directed adjacency list without adding reverse edges computes neither: it computes reachability from whichever vertices the sweep happens to start at, a subtle bug that passes tests on symmetric inputs.

The two notions nest. Every strongly connected component lies inside exactly one weakly connected component, so a cheap weak labelling is a useful first pass on a big directed graph: it splits the work into independent pieces that can be handed to an SCC algorithm one at a time, or in parallel. The arcs 1 to 2 and 3 to 2, for example, form one weak component but three strong ones, because no vertex can reach back to another.

When edges are deleted

Insertions are easy: union the endpoints. Deletions are hard, because removing an edge may or may not split a component and finding out requires knowing whether another path exists. There are three practical answers. Recompute from scratch, which is O(V + E) and often fine if deletions are batched. If the full sequence of operations is known in advance, process it offline: union-find with rollback over a segment tree of edge lifetimes handles each edge in O(log) unions. Or use a fully dynamic connectivity structure; Holm, de Lichtenberg and Thorup gave one with O(log² n) amortised time per update, but its constants and complexity mean it is rarely worth implementing unless deletions dominate and recomputation is too slow.

Components at scale

When the graph is spread across machines, the dominant cost is communication rounds, not operations. The simplest distributed method is min-label propagation: each vertex starts with its own id as label, and every round it adopts the smallest label among itself and its neighbours. It converges when no label changes. It maps directly onto vertex-centric systems such as Pregel and Spark GraphX, but needs as many rounds as the largest component diameter, which is disastrous on long chains.

# One synchronous round of min-label propagation over an edge list.
def propagate(labels, edges):
    new = labels[:]
    for u, v in edges:
        m = min(labels[u], labels[v])
        if m < new[u]: new[u] = m
        if m < new[v]: new[v] = m
    return new

def label_propagation(n, edges, max_rounds=10_000):
    labels = list(range(n))
    for _ in range(max_rounds):
        nxt = propagate(labels, edges)
        if nxt == labels:
            return labels
        labels = nxt
    raise RuntimeError("did not converge; graph diameter exceeds max_rounds")

The Shiloach-Vishkin family fixes the round count with two moves: hooking, where the root of one tree is attached to a smaller-labelled root across an edge, and pointer jumping, where every vertex replaces its parent with its grandparent, halving tree depth each round. Together they converge in O(log n) rounds. Modern GPU and shared-memory implementations such as Afforest also sample a few edges per vertex first to find the giant component cheaply, then skip most edges inside it. On one large machine, though, a well-written union-find over a compressed edge list often beats a distributed job outright; measure before reaching for a cluster.

Failure modes

Trade-offs

What to do next

1. Implement the iterative labeller above and test it on a 1,000,000-vertex path to confirm it does not recurse.
2. Add a test with isolated vertices and assert the component count includes them.
3. Re-implement the same labelling with the DSU class over a shuffled edge list and check both give the same partition.
4. For directed data, decide whether you need weak or strong components and choose the algorithm accordingly.
5. If edges are deleted, measure full recomputation time before considering dynamic structures.
6. For graphs beyond one machine, estimate diameter before choosing label propagation.
7. Continue with BFS and DFS for the traversal details these methods rest on.