Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 5

A connected component of an undirected graph is a maximal set of vertices such that each pair is joined by a path. Equivalently, components are the equivalence classes of the relation “reachable by a path”. The length-zero path ensures that an isolated vertex is a one-vertex component.

Start a depth-first search from each as-yet unlabelled vertex, propagating a fresh component number:A search follows only edges, so every vertex it labels is reachable from its root. Conversely, if a reachable vertex remained unlabelled, a path to it would contain a first edge from a visited vertex to an unvisited one; scanning that edge would visit the latter, a contradiction. Thus each search labels exactly one connected component, proving both directions of the required equivalence.

With an adjacency list, initialization and the outer loop cost $O(|V|)$. Each vertex is visited once, and the adjacency scans inspect each edge of a graph twice, once from each endpoint. The total worst-case time is therefore $O(|V|+|E|)$, with $O(|V|)$ labels and recursion-stack space. An adjacency matrix representation instead incurs $O(|V{|}^2)$ scanning time.

A disjoint-set data structure maintains a partition of a set into pairwise disjoint sets. Make-Set(v) creates the singleton containing a new vertex. Find-Set(v) returns the disjoint-set representative of its current set. Union(u,v) merges the two sets containing its arguments, preserving the partition; it has no effect if they are already the same set. A disjoint-set forest can implement these operations without explicitly moving every member when sets are joined.

Test Find-Set(u) == Find-Set(v). Initially the sets are singleton connected components of the edgeless graph; processing an edge joins precisely the components it connects. By induction over the processed edges, the final sets are exactly the connected components of $G$.

The displayed procedure calls Find-Set $2|E|$ times explicitly, since it tests the two endpoints of every edge. Each successful Union decreases the number of sets by one, from $|V|$ initially to $k$ finally, so there are $|V|-k$ Union calls.

These are calls at the displayed pseudocode level. If a concrete Union(u,v) implementation performs two further internal finds rather than accepting already found roots, its implementation adds $2(|V|-k)$ find invocations. Counting those separately avoids confusing the procedure's explicit call count with the implementation of a disjoint-set union operation.