Conjunto disjunto (algoritmo de búsqueda de unión) en PHP

Publicado: 16 de febrero de 2025, 12:25:04 UTC
Última actualización: 26 de enero de 2026, 10:36:44 UTC

Este artículo presenta una implementación en PHP de la estructura de datos Disjoint Set, comúnmente utilizada para Union-Find en algoritmos de árbol de expansión mínima.

Esta página ha sido traducida automáticamente del inglés para hacerla accesible al mayor número de personas posible. Lamentablemente, la traducción automática no es todavía una tecnología perfeccionada, por lo que pueden producirse errores. Si lo prefiere, puede consultar la versión original en inglés aquí:

Disjoint Set (Union-Find Algorithm) in PHP

El Conjunto Disconjunto (comúnmente utilizado para Union-Finger, también conocido como Unión de Conjuntos Disjoint) es una estructura de datos utilizada para gestionar una partición de elementos en conjuntos disjuntos (no solapados). Soporta dos operaciones clave de forma eficiente:

Find: Determina a qué conjunto pertenece un elemento.
Unión: Fusiona dos conjuntos.

Esta estructura es especialmente útil en algoritmos de árbol generador mínimo, como el algoritmo de Kruskal.

Tengo una implementación del algoritmo de Kruskal usada para generar laberintos aleatorios que se basa en la implementación de PHP de Disjoint Set para fusionar conjuntos de forma eficiente. Si te interesa, puedes verlo en acción aquí: Generador de laberintos del algoritmo de Kruskal

En fin, esta es mi implementación en 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]++;
            }
        }
    }
}

Además de generar laberintos por diversión, la estructura de datos del Conjunto Disconjunto también puede usarse en escenarios reales.

Imagina, por ejemplo, una red social que quisiera sugerir nuevos amigos a sus usuarios, y luego supongamos que tenemos seis personas con estas relaciones de amistad ya establecidas:

1 y 2 son amigos.
2 y 3 son amigos.
4 y 5 son amigos.
6 no tiene amigos.

Aplicando el algoritmo Union-Find a estos grupos separados, deberíamos encontrar lo siguiente:

1, 2 y 3 en un mismo grupo.
4 y 5 en un segundo grupo.
6 en un tercer grupo.

Con base en esto, tendría sentido sugerir que el 1 y el 3 deberían hacerse amigos, porque tienen a la persona 2 en común.

Por supuesto, en un pequeño ejemplo como este, podrías detectar fácilmente este hecho tú mismo, pero la eficiencia de este algoritmo permite que escale de forma factible a miles de millones de personas y grupos de amigos.