Ensemble disjoint (algorithme Union-Find) en PHP

Publié : 16 février 2025 à 12 h 35 min 04 s UTC

Cet article présente une implémentation PHP de la structure de données d’ensemble disjoint, généralement utilisée pour l’Union-Find dans les algorithmes de spanning-tree minimum.

Cette page a été automatiquement traduite de l'anglais afin de la rendre accessible au plus grand nombre. Malheureusement, la traduction automatique n'est pas encore une technologie au point, des erreurs peuvent donc survenir. Si vous préférez, vous pouvez consulter la version originale en anglais ici :

Disjoint Set (Union-Find Algorithm) in PHP

L’ensemble disjoint (couramment utilisé pour Union-Find alias Union d’ensemble disjoint) est une structure de données utilisée pour gérer une partition d’éléments en ensembles disjoints (non superposés). Il soutient efficacement deux opérations clés :

Rechercher : détermine à quel ensemble un élément appartient.
Union : fusionne deux ensembles.

Cette structure est particulièrement utile dans les algorithmes de spanning-tree minimum, tels que l’algorithme de Kruskal.

J’ai une implémentation de l’algorithme de Kruskal utilisé pour générer des labyrinthes aléatoires qui s’appuie sur l’implémentation PHP ci-dessous de Disjoint Set pour fusionner efficacement les ensembles. Si vous êtes intéressé, vous pouvez le voir en action ici : Générateur de labyrinthe d’algorithme de Kruskal

Quoi qu’il en soit, c’est mon implémentation 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]++;
            }
        }
    }
}

En plus de générer des labyrinthes pour le plaisir, la structure de données Disjoint Set peut certainement également être utilisée pour des scénarios réels.

Imaginez, par exemple, un réseau social qui aimerait suggérer de nouveaux amis à ses utilisateurs, puis disons que nous avons six personnes avec ces relations d’amis déjà en place :

1 et 2 sont amis.
2 et 3 sont amis.
4 et 5 sont amis.
6 n’a pas d’amis.

En appliquant l’algorithme Union-Find à ces groupes distincts, nous devrions trouver ce qui suit :

1, 2 et 3 dans un groupe.
4 et 5 dans un deuxième groupe.
6 dans un troisième groupe.

Sur cette base, il serait logique de suggérer que 1 et 3 devraient devenir amis, car ils ont la personne 2 en commun.

Bien sûr, dans un petit exemple comme celui-ci, vous pourriez facilement repérer ce fait vous-même, mais l’efficacité de cet algorithme lui permet de s’adapter à des milliards de personnes et de groupes d’amis.