Disjoint Sets

Note

Objectives

1. Trace Kruskal's algorithm to find a minimum spanning tree in a graph.
2. Compare Kruskal's algorithm runtime on different disjoint sets implementations.
3. Describe opportunities to improve algorithm efficiency by identifying bottlenecks.

Code: QuickFindUF.java, QuickUnionUF.java, WeightedQuickUnionUF.java

Prim's uses the same graph algorithm design pattern as breadth-first search (BFS) and Dijkstra's algorithm. All three algorithms:

• use a queue or a priority queue to determine the next vertex to visit,
• finish when all the reachable vertices have been visited,
• and depend on a neighbors method to gradually explore the graph vertex-by-vertex.

Even depth-first search (DFS) relies on the same pattern. Instead of iterating over a queue or a priority queue, DFS uses recursive calls to determine the next vertex to visit. But not all graph algorithms share this same pattern.

Kruskal's algorithm

Kruskal's algorithm is another algorithm for finding a minimum spanning tree (MST) in a graph. Kruskal's algorithm has just a few steps:

1. Given a list of the edges in a graph, sort the list of edges by their edge weights.
2. Build up a minimum spanning tree by considering each edge from least weight to greatest weight.
   1. Check if adding the current edge would introduce a cycle.
   2. Add the edge to the MST only if it doesn't introduce a cycle.

The algorithm is done when $|V| - 1$ edges have been added to the growing MST.

You can think of Kruskal's algorithm as another way of repeatedly applying the cut property. But instead of growing the MST outward from a single start vertex, Kruskal's algorithm grows many independent connected components, or disjoint (non-overlapping) sets of vertices that are connected to each other.

Informally, you can think of each connected component as its own island. Initially, each vertex is its own island. These independent islands are gradually connected to neighboring islands by choosing the next-smallest weight edge that doesn't introduce a cycle. In the following slide (from Minimum Spanning Trees by Robert Sedgewick and Kevin Wayne):

• Case 2 on the left of the slide shows how adding an edge $(v, w)$ creates a cycle within a connected component
• Case 1 on the right of the slide shows how adding an edge $(v, w)$ merges two connected components, forming a larger connected component.

Kruskal's algorithm needs a way to efficiently keep track of all the connected components. The disjoint sets (aka union-find) abstract data type is used to maintain the state of connected components. Specifically, our disjoint sets data type stores all the vertices in a graph as elements. A Java interface for disjoint sets might include two methods:

• A find(v) method that returns the representative for the given vertex. In Kruskal's algorithm, we only add the current edge to the result if find(v) != find(w).
• A union(v, w) method that connects the two vertices $v$ and $w$. In Kruskal's algorithm, this keeps track of the fact that we joined the two connected components.

Using this DisjointSets data type, we can now implement Kruskal's algorithm.

kruskalMST(Graph<V> graph) {
    // Create a DisjointSets implementation storing all vertices
    DisjointSets<V> components = new DisjointSetsImpl<V>(graph.vertices());
    // Get the list of edges in the graph
    List<Edge<V>> edges = graph.edges();
    // Sort the list of edges by weight
    edges.sort(Double.comparingDouble(Edge::weight));

    List<Edge<V>> result = new ArrayList<>();
    int i = 0;
    while (result.size() < graph.vertices().size() - 1) {
        Edge<V> e = edges.get(i);
        if (!components.find(e.from).equals(components.find(e.to))) {
            components.union(e.from, e.to);
            result.add(e);
        }
        i += 1;
    }
    return result;
}

Data structures

How do we implement DisjointSets?

Important

Review the Union-Find slides.

Then, review the Quick-Union Demo and finally the Weighted Quick-Union slides.

What are the three implementations and their general characteristics?

1. Quick-find optimizes for the find operation.
2. Quick-union optimizes for the union operation, but doesn't really succeed.
3. Weighted quick-union addresses the worst-case height problem introduced in quick-union.