Union-Find Algorithm

The Union-Find algorithm is designed to solve "dynamic connectivity" problems. I have written about it before, because it is often tested and is also a key part of minimum spanning tree algorithms. So I put together this article to explain Union-Find clearly in one place.

Let's start by understanding what dynamic connectivity in a graph means.

1. Dynamic Connectivity

Simply put, dynamic connectivity means connecting nodes in a graph. For example, in the graph below, there are 10 nodes, not connected to each other, labeled 0 to 9:

Now, our Union-Find algorithm mainly needs to provide these two APIs:

class UF {
    // connect p and q
    public void union(int p, int q);
    // determine if p and q are connected
    public boolean connected(int p, int q);
    // return the number of connected components in the graph
    public int count();
}

class UF {
public:
    // connect p and q
    void union_(int p, int q) = 0;

    // determine if p and q are connected
    bool connected(int p, int q) = 0;

    // return the number of connected components in the graph
    int count() = 0;
};

class UF:
    # connect p and q
    def union(self, p, q):
        pass
    
    # determine if p and q are connected
    def connected(self, p, q):
        pass

    # return the number of connected components in the graph
    def count(self):
        pass

type UF struct{}
// connect p and q
func (uf *UF) Union(p int, q int) {}
// determine if p and q are connected
func (uf *UF) Connected(p int, q int) bool {
   return false
}
// return the number of connected components in the graph
func (uf *UF) Count() int {
   return 0
}

var UF = function() {
    // connect p and q
    this.union = function(p, q) {}; 

    // determine if p and q are connected
    this.connected = function(p, q) {};

    // return the number of connected components in the graph
    this.count = function() {};
};

Here, "connected" is an equivalence relation. It has three properties:

1. Reflexivity: Node p is connected to itself.

2. Symmetry: If node p is connected to q, then q is also connected to p.

3. Transitivity: If node p is connected to q, and q is connected to r, then p is connected to r.

For example, in the graph above, any two different nodes from 0 to 9 are not connected. Calling connected returns false, and there are 10 connected components.

If we call union(0, 1), then 0 and 1 become connected, and the number of connected components drops to 9.

Next, call union(1, 2). Now, 0, 1, and 2 are all connected. Calling connected(0, 2) returns true, and there are 8 connected components.

Checking this kind of "equivalence relation" is very useful. For example, a compiler checks references to the same variable, or social networks calculate friend circles.

So now you should have a rough idea of what dynamic connectivity is. The key to the Union-Find algorithm is how fast the union and connected functions are. But how should we model the connections in the graph? What data structure should we use in code?

2. Basic Idea

3. Balancing Optimization

4. Path Compression