Connected components

Cost and properties

preprocess	O(V + E)
query	O(1) — constant
vs union-find	same answer, different setting
gives	an id per vertex

Reference: Sedgewick & Wayne, §4.1.

Connected components in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

class ConnectedComponents:
    # id[v] is the component number of v, so connected(v, w) is one
    # comparison after a single linear-time pass.

    def __init__(self, graph):
        self.marked = [False] * graph.V
        self.id = [-1] * graph.V
        self.count = 0
        for v in range(graph.V):
            if not self.marked[v]:        # no earlier search reached v,
                self._dfs(graph, v)       # so v starts a NEW component
                self.count += 1

    def _dfs(self, graph, v):
        self.marked[v] = True
        self.id[v] = self.count
        for w in graph.adj(v):
            if not self.marked[w]:
                self._dfs(graph, w)

    def connected(self, v, w):
        return self.id[v] == self.id[w]

Why it works

The outer loop is the idea

DFS marks everything reachable from where it starts. So if a vertex is still unmarked after all earlier searches, nothing already seen can reach it — it must be in a new component. The outer loop therefore runs DFS exactly count times, and the total work is still O(V + E) because each vertex and edge is handled once overall.

Preprocessing buys constant queries

Answering “are v and w connected?” by searching costs O(V + E) per query. One linear pass that fills id[] makes every later query a single comparison. When you expect many queries, preprocessing into an array is almost always the right shape — and it is the same reasoning behind rank/select in a BST.

Versus union-find

Both answer connectivity queries in near-constant time. The difference is when the edges arrive: union-find handles a stream of new edges arriving over time (dynamic connectivity) but cannot produce a path; DFS needs the whole graph up front but also gives you paths, cycles and much more structure. Choose by the interface you must support, not by speed.

Real uses

Flood fill and “number of islands”, image blob detection (pixels as vertices, adjacent similar pixels as edges), particle detection in medical images, and dividing a large graph into independent pieces so the rest of your analysis can run per component.

What to try in the animation

The default is tinyG.txt from the course: 13 vertices in 3 components.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• tinyG — 3 components — vertices: 13 · edges: 0-5 4-3 0-1 9-12 6-4 5-4 0-2 11-12 9-10 0-6 7-8 9-11 5-3 · source: 0
• one component — vertices: 6 · edges: 0-5 2-4 2-3 1-2 0-1 3-4 3-5 0-2 · source: 0
• three pairs — vertices: 6 · edges: 0-1 2-3 4-5
• two big blobs — vertices: 10 · edges: 0-1 1-2 2-3 3-0 0-2 5-6 6-7 7-8 8-9 9-5

Open Connected components in the player →

The rest of Undirected graphs

• Depth-first search Mark a vertex, then recur into any unmarked neighbour.
• Breadth-first search Swap the recursion for a queue and vertices come off in order of distance.