Conjunt disjunt (algoritme Union-Find) en PHP

Publicat: 5 de març del 2025, a les 19:31:12 UTC
Última actualització: 26 de gener del 2026, a les 10:37:18 UTC

Aquest article presenta una implementació PHP de l'estructura de dades Disjoint Set, comunament utilitzada per a Union-Find en algoritmes d'arbre generador mínim.

Aquesta pàgina es va traduir automàticament de l'anglès per tal de fer-la accessible al màxim de persones possible. Malauradament, la traducció automàtica encara no és una tecnologia perfeccionada, de manera que es poden produir errors. Si ho prefereixes, pots veure la versió original en anglès aquí:

Disjoint Set (Union-Find Algorithm) in PHP

El Conjunt Disconjunt (comunament utilitzat per a Union-Finger, també conegut com a Unió de Conjunts Disjunts) és una estructura de dades utilitzada per gestionar una partició d'elements en conjunts disjunts (no superposats). Suporta dues operacions clau de manera eficient:

Trobar: Determina a quin conjunt pertany un element.
Unió: Fusiona dos conjunts.

Aquesta estructura és especialment útil en algorismes d'arbre generador mínim, com l'algorisme de Kruskal.

Tinc una implementació de l'algorisme de Kruskal utilitzat per generar laberints aleatoris que es basa en la implementació PHP següent de Disjoint Set per fusionar conjunts de manera eficient. Si t'interessa, ho pots veure en acció aquí: Generador de laberints d'algoritmes de Kruskal

En fi, aquesta és la meva implementació PHP de 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]++;
            }
        }
    }
}

A més de generar laberints per diversió, l'estructura de dades Disjoint Set també es pot utilitzar en escenaris reals.

Imagina, per exemple, una xarxa social que voldria suggerir nous amics als seus usuaris, i després suposem que tenim sis persones amb aquestes relacions d'amistat ja establertes:

L'1 i el 2 són amics.
El 2 i el 3 són amics.
Els 4 i 5 són amics.
6 no té amics.

Aplicant l'algorisme Union-Find a aquests grups separats, hauríem de trobar el següent:

1, 2 i 3 en un mateix grup.
4 i 5 en un segon grup.
6 en un tercer grup.

Basat en això, tindria sentit suggerir que l'1 i el 3 haurien de fer-se amics, perquè tenen la persona 2 en comú.

És clar, en un exemple petit com aquest, podries detectar fàcilment aquest fet tu mateix, però l'eficiència d'aquest algoritme permet que escali de manera factible a milers de milions de persones i grups d'amics.