Ensemble disjoint (algorithme Union-Find) en PHP

Publié : 16 février 2025 à 12:25:22 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 d'arbre couvrant minimum.

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-Find ou Disjoint Set Union) est une structure de données utilisée pour gérer une partition d'éléments en ensembles disjoints (non superposés). Il prend en charge efficacement deux opérations clés :

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

Cette structure est particulièrement utile dans les algorithmes d'arbre couvrant minimal, 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 des ensembles. Si vous êtes intéressé, vous pouvez le voir en action ici : Générateur de labyrinthe avec l'algorithme de Kruskal

Quoi qu'il en soit, 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]++;
            }
        }
    }
}

Outre la génération de 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 voudrait suggérer de nouveaux amis à ses utilisateurs, et disons que nous avons six personnes avec ces relations d'amitié 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 deviennent amis, car ils ont la personne 2 en commun.

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