Ensemble disjoint (algorithme Union-Find) en PHP

Publié : 16 février 2025 à 12 h 35 min 04 s UTC
Dernière mise à jour : 26 janvier 2026 à 10 h 37 min 22 s 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 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-Finger, aussi appelé Disjoint Set Union) est une structure de données utilisée pour gérer une partition d’éléments en ensembles disjoints (non chevauchants). Il supporte 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, comme 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 ça vous intéresse, vous pouvez le voir en action ici : Générateur de labyrinthe d’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, et disons que nous avons déjà six personnes ayant ces relations d’amis en place :

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

En appliquant l’algorithme Union-Find à ces groupes séparés, on devrait 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, parce qu’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’étendre à des milliards de personnes et de groupes d’amis.