Ensemble disjoint (algorithme Union-Find) en PHP

Publié : 16 février 2025 à 12:25:22 UTC
Dernière mise à jour : 26 janvier 2026 à 10:36:48 UTC

Cet article présente une implémentation PHP de la structure de données Disjoint Set, couramment utilisée pour Union-Find dans les algorithmes à arbre couvrant minimal.

Cette page a été traduite de l'anglais afin de la rendre accessible au plus grand nombre. Malheureusement, la traduction automatique n'est pas encore une technologie parfaite, et des erreurs peuvent donc se produire. 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-Finger, également appelé Union d’ensembles disjoints) est une structure de données utilisée pour gérer une partition d’éléments en ensembles disjoints (non chevauchants). Il prend en charge efficacement deux opérations clés :

Trouver : Détermine à quel ensemble appartient un élément.
Union : Fusionne deux ensembles.

Cette structure est particulièrement utile dans les algorithmes à arbre couvrant minimal, tels que l’algorithme de Kruskal.

J’ai une implémentation de l’algorithme de Kruskal utilisée 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 cela vous intéresse, vous pouvez le voir en action ici : Générateur de labyrinthe avec l'algorithme de Kruskal

Bref, voici 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 aussi être utilisée dans des scénarios réels.

Imaginez, par exemple, un réseau social qui souhaite suggérer de nouveaux amis à ses utilisateurs, puis supposons que nous ayons déjà six personnes ayant ces relations d’amis :

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 séparés, nous devrions trouver ce qui suit :

1, 2 et 3 dans un même 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 deviennent amis, car ils ont une 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’étendre de manière réaliste à des milliards de personnes et de groupes d’amis.