Conjunt disjunt (algoritme Union-Find) en PHP

Publicat: 5 de març del 2025, a les 19:31:12 UTC

Aquest article inclou una implementació PHP de l'estructura de dades Disjoint Set, que s'utilitza habitualment per a Union-Find en algorismes d'arbre d'abast 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 disjunt (utilitzat habitualment per a Union-Find, també conegut com a Disjoint Set Union) és una estructura de dades que s'utilitza per gestionar una partició d'elements en conjunts disjunts (no superposats). Admet dues operacions clau de manera eficient:

Cerca : determina a quin conjunt pertany un element.
Unió : fusiona dos conjunts.

Aquesta estructura és particularment útil en algorismes d'arbre d'abast mínim, com ara l'algoritme de Kruskal.

Tinc una implementació de l'algorisme de Kruskal que s'utilitza per generar laberints aleatoris que es basa en la implementació PHP següent de Disjoint Set per combinar conjunts de manera eficient. Si esteu interessats, podeu veure-ho en acció aquí: Generador de laberints d'algoritmes de Kruskal

De totes maneres, 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 part de generar laberints per diversió, l'estructura de dades del conjunt disjunt també es pot utilitzar per a escenaris de la vida real.

Imagineu, per exemple, una xarxa social que vol suggerir nous amics als seus usuaris i, aleshores, diguem que ja tenim sis persones amb aquestes relacions d'amistat:

1 i 2 són amics.
2 i 3 són amics.
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 sol grup.
4 i 5 en un segon grup.
6 en un tercer grup.

A partir d'això, tindria sentit suggerir que l'1 i el 3 es fessin amics, perquè tenen la persona 2 en comú.

Per descomptat, en un petit exemple com aquest, podríeu detectar fàcilment aquest fet, però l'eficiència d'aquest algorisme li permet escalar de manera viable a milers de milions de persones i grups d'amics.