Union-Find Algorithm

The Union-Find algorithm is specifically designed for "dynamic connectivity." I have written about it twice before. Due to its high frequency in exams and its role as a prerequisite for minimum spanning tree algorithms, I have consolidated this article to explain the algorithm clearly in one go.

First, let's start with what dynamic connectivity in graphs is.

I. Dynamic Connectivity

Simply put, dynamic connectivity can be abstracted as connecting lines in a graph. For example, in the following graph, there are 10 nodes that are not connected to each other, labeled from 0 to 9:

Now, our Union-Find algorithm mainly needs to implement 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() {};
};

The term "connected" here refers to an equivalence relation, which means it has the following three properties:

1. Reflexivity: Node p is connected to itself.

2. Symmetry: If node p is connected to node q, then q is 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 previous graph, any two different points from 0 to 9 are not connected, and calling connected will return false, resulting in 10 connected components.

If we now call union(0, 1), then 0 and 1 become connected, reducing the connected components to 9.

Calling union(1, 2) next will make 0, 1, and 2 connected, and calling connected(0, 2) will return true, reducing the connected components to 8.

Determining such an "equivalence relation" is very practical, such as compilers determining different references of the same variable, or calculating friend circles in social networks, etc.

Now, you should have a rough understanding of what dynamic connectivity is. The key to the Union-Find algorithm lies in the efficiency of the union and connected functions. So, what model represents the connectivity of this graph? What data structure should be used to implement the code?

II. Basic Ideas

III. Balancing Optimization

IV. Path Compression