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

Publicado: 16 de febrero de 2025, 12:25:04 UTC

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

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 disjunto (que se utiliza habitualmente para la búsqueda de uniones, también conocido como unión de conjuntos disjuntos) es una estructura de datos que se utiliza para gestionar una partición de elementos en conjuntos disjuntos (no superpuestos). Admite dos operaciones clave de manera eficiente:

Buscar : determina a qué conjunto pertenece un elemento.
Unión : Fusiona dos conjuntos.

Esta estructura es particularmente útil en algoritmos de árbol de expansión mínimo, como el algoritmo de Kruskal.

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

De todos modos, esta es mi implementación 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 disjunto también se puede utilizar para escenarios de la vida real.

Imaginemos, por ejemplo, una red social que quisiera sugerir nuevos amigos a sus usuarios y digamos 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 grupo.
4 y 5 en un segundo grupo.
6 en un tercer grupo.

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

Por supuesto, en un ejemplo pequeño como este, usted mismo podría detectar fácilmente este hecho, pero la eficiencia de este algoritmo le permite escalar de manera factible a miles de millones de personas y grupos de amigos.