Data Structures & Algorithms / Optimization proofs and maintained aggregates / Lesson 15

Disjoint sets and minimum spanning forests

Maintain component representatives and use a cut-based greedy rule without confusing connectivity with shortest paths.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

A representative names a component, not a graph path
Attach the smaller component beneath the larger
Kruskal accepts the lightest safe component connection

A representative names a component, not a graph path

Disjoint-set union maintains a partition of elements into components. find returns a representative, and union merges components when their representatives differ. The parent forest is an internal representation, not necessarily a path in the original graph. Path compression may change that forest without changing component membership. Applications should compare representatives for equality rather than depending on one particular root identifier. These examples use vertices numbered0 through n-1 and reject unknown indices. The structure supports merging, not arbitrary edge deletion that might split a component; that requires a different dynamic-connectivity contract.

Attach the smaller component beneath the larger

The first program combines union by size with path halving. Whenever union adds a parent edge, an element in the smaller component enters a component at least twice as large. Without even relying on compression, this gives logarithmic depth. Compression only shortens paths. Stronger amortized bounds exist for these combined techniques, but a coarse O(log n) bound per operation suffices for this lesson’s implementation analysis. Root sizes are authoritative only at representatives; do not read a stale size field on a nonroot as the current component size. A failed union returns False because no new connection was needed.

python Self-contained Python3 algorithm example using synthetic local data.

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
    def find(self, vertex):
        if not 0 <= vertex < len(self.parent):
            raise ValueError("Unknown vertex")
        while self.parent[vertex] != vertex:
            self.parent[vertex] = self.parent[self.parent[vertex]]
            vertex = self.parent[vertex]
        return vertex
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        return True

sets = DisjointSet(4)
print(sets.union(0, 1))
print(sets.union(1, 0))
print(sets.find(0) == sets.find(1))
print(sets.find(0) == sets.find(2))

Expected output

True
False
True
False

Repeated union preserves the partition. The particular representative number is not part of the external contract.

Kruskal accepts the lightest safe component connection

A minimum spanning tree connects all vertices of a connected undirected weighted graph with minimum total edge weight and no cycle. Kruskal processes edges by nondecreasing weight and accepts an edge only when it joins different current components. The cut property justifies choosing a lightest crossing edge for a cut respecting accepted edges. Disjoint sets answer the cycle question efficiently; they do not prove minimality by themselves. Negative edge weights are allowed for this problem. If the graph is disconnected, the same procedure returns a minimum spanning forest, and the component count must remain visible rather than falsely declaring one spanning tree.

python Self-contained Python3 algorithm example using synthetic local data.

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
    def find(self, x):
        if not 0 <= x < len(self.parent):
            raise ValueError("Unknown vertex")
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        return True

def kruskal(n, edges):
    if n < 0:
        raise ValueError("Vertex count must be nonnegative")
    if any(not (0 <= a < n and 0 <= b < n) for _, a, b in edges):
        raise ValueError("Unknown vertex")
    sets = DisjointSet(n)
    total, chosen, components = 0, [], n
    for weight, a, b in sorted(edges):
        if sets.union(a, b):
            total += weight
            chosen.append((a, b))
            components -= 1
    return total, chosen, components

print(kruskal(4, [(1,0,1), (4,0,2), (2,1,2), (3,2,3), (7,1,3)]))
print(kruskal(3, [(2,0,1)]))

Expected output

(6, [(0, 1), (1, 2), (2, 3)], 1)
(2, [(0, 1)], 2)

The first graph yields a tree of weight6. The second has two components and therefore yields a forest.

Do not confuse spanning objectives with distance objectives

A minimum spanning tree minimizes the sum of selected connection costs over the whole network. A shortest-path tree minimizes source-to-vertex distances under a different objective. Neither guarantee implies the other. The selected tree’s path between two vertices may be longer than another path in the original graph. Similarly, a disjoint-set parent chain is not a recovered route through accepted edges. Keep a separate chosen-edge adjacency representation when the application needs actual forest paths. Equal-weight alternatives can yield several equally optimal spanning forests, so test objective value and structural validity rather than a unique edge sequence unless tie order is specified.

Account for sorting and represented isolated vertices

Sorting E edges costs O(E log E) comparisons in the ordinary model. With the coarse union-by-size bound, component operations add O(E log V), and initialization costs O(V). This statement also covers parallel edges without silently assuming E is bounded by V squared. The arrays use O(V) space, the accepted forest uses at most V-1 edges when V is positive, and sorting has its own storage cost. Isolated vertices count as components even though they occur in no edge. A self-loop never merges distinct representatives and is therefore safely rejected by the union test.

Check partitions and forest optimality independently

Compare component membership after small union sequences with a naive label-based partition. For tiny graphs, enumerate candidate acyclic spanning subsets and compare total weight within each original component. Verify chosen edges belong to the input, produce no cycle, and give exactly V-components accepted edges. Include duplicate edges, negative weights, equal weights, self-loops, and disconnected vertices. Do not require one root number or one tied optimum. Bounded enumeration complements the cut argument and keeps all validation as small local computations without operating a real network or graph service.

Common errors and fixes

Internal parent links are displayed as original graph paths

Why it happens: Representative structure was confused with selected edges.
How to fix it: Retain accepted edges separately for route reconstruction.
Prevent it next time: Check every displayed path edge against the original graph.

A disconnected result is called a spanning tree

Why it happens: Component count was discarded after processing.
How to fix it: Return the forest status or reject disconnected input under a tree-only contract.
Prevent it next time: Include an isolated vertex fixture.

Root identity is treated as permanent membership data

Why it happens: Union and compression may change representatives.
How to fix it: Compare current finds or expose a separate stable domain identifier.
Prevent it next time: Test unions in different orders.

Check your understanding

1. Why can union by size bound depth before compression is considered?

Show worked solution

Each time a node’s component is attached below another, its containing component at least doubles in size. Starting from size1, this can happen at most logarithmically many times before reaching at most n. Compression only shortens those paths.

2. Why is a negative edge valid for Kruskal but problematic for Dijkstra?