Disjoint Set (Union-Find Algorithm) in PHP

Published: February 3, 2025 at 5:26:16 PM UTC

This article features a PHP implementation of the Disjoint Set data structure, commonly used for Union-Find in minimum spanning tree algorithms.

The Disjoint Set (commonly used for Union-Find a.k.a. Disjoint Set Union) is a data structure used to manage a partition of elements into disjoint (non-overlapping) sets. It supports two key operations efficiently:

Find: Determines which set an element belongs to.
Union: Merges two sets together.

This structure is particularly useful in minimum spanning tree algorithms, such as Kruskal's algorithm.

I have an implementation of Kruskal's algorithm used for generating random mazes that relies on the below PHP implementation of Disjoint Set to efficiently merge sets. If you're interested, you can see it in action here: Kruskal's Algorithm Maze Generator

Anyway, this is my PHP implementation of Disjoint Set:

class DisjointSet 
{
    private $parent = [];
    private $rank   = [];

    public function __construct($size) 
    {
        for ($i = 0; $i < $size; $i++) 
        {
            $this->parent[$i]   = $i;
            $this->rank[$i]     = 0;
        }
    }

    public function find($x) 
    {
        if ($this->parent[$x] != $x) 
        {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }

        return $this->parent[$x];
    }

    public function union($x, $y) 
    {
        $rootX = $this->find($x);
        $rootY = $this->find($y);

        if ($rootX != $rootY) 
        {
            if ($this->rank[$rootX] > $this->rank[$rootY]) 
            {
                $this->parent[$rootY] = $rootX;
            }
            elseif ($this->rank[$rootX] < $this->rank[$rootY]) 
            {
                $this->parent[$rootX] = $rootY;
    
            }
            else
            {
                $this->parent[$rootY] = $rootX;
                $this->rank[$rootX]++;
            }
        }
    }
}

Apart from generating mazes for fun, the Disjoint Set data structure can certainly also be used for real-life scenarios.

Imagine, for example, a social network that would like to suggest new friends to its users, and then let's say that we have six people with these friend relationships already in place:

1 and 2 are friends.
2 and 3 are friends.
4 and 5 are friends.
6 has no friends.

Applying the Union-Find algorithm to these separate groups, we should find the following:

1, 2 and 3 in one group.
4 and 5 in a second group.
6 in a third group.

Based on this, it would make sense to suggest that 1 and 3 should become friends, because they have person 2 in common.

Of course, in a small example like this, you could easily spot this fact yourself, but the efficiency of this algorithm allows it to feasibly scale to billions of people and friend groups.