Conjunto Disjunto (Union-Find Algorithm) em PHP

Publicado: 16 de fevereiro de 2025 às 12:26:46 UTC

Este artigo apresenta uma implementação PHP da estrutura de dados Disjoint Set, comummente utilizada para o Union-Find em algoritmos de árvores de extensão mínima.

Esta página foi traduzida automaticamente do inglês para a tornar acessível ao maior número possível de pessoas. Infelizmente, a tradução automática ainda não é uma tecnologia aperfeiçoada, pelo que podem ocorrer erros. Se preferir, pode ver a versão original em inglês aqui:

Disjoint Set (Union-Find Algorithm) in PHP

O Disjoint Set (comumente utilizado para Union-Find, também conhecido como Disjoint Set Union) é uma estrutura de dados utilizada para gerir uma partição de elementos em conjuntos disjuntos (não sobrepostos). Suporta um suporte eficiente a duas operações principais:

Localizar : Determina a que conjunto pertence um elemento.
União : Mescla dois conjuntos.

Esta estrutura é particularmente útil em algoritmos de árvores de abrangência mínima, como o algoritmo de Kruskal.

Tenho uma implementação do algoritmo de Kruskal utilizado para gerar labirintos aleatórios que se baseia na implementação PHP abaixo do Disjoint Set para fundir conjuntos de forma eficiente. Se estiver interessado, pode vê-lo em ação aqui: Gerador de labirintos do algoritmo de Kruskal

De qualquer forma, esta é a minha implementação PHP do 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]++;
            }
        }
    }
}

Além de gerar labirintos por diversão, a estrutura de dados Disjoint Set pode certamente também ser utilizada em cenários da vida real.

Imagine-se, por exemplo, uma rede social que gostaria de sugerir novos amigos aos seus utilizadores, e então digamos que temos seis pessoas com estas relações de amizade já estabelecidas:

1 e 2 são amigos.
2 e 3 são amigos.
4 e 5 são amigos.
6 não tem amigos.

Aplicando o algoritmo Union-Find a estes grupos separados, devemos encontrar o seguinte:

1, 2 e 3 num grupo.
4 e 5 num segundo grupo.
6 num terceiro grupo.

Com base nisto, faria sentido sugerir que 1 e 3 se tornassem amigos, porque têm a pessoa 2 em comum.

Claro que, num pequeno exemplo como este, poderia facilmente identificar este facto por si mesmo, mas a eficiência deste algoritmo permite que seja dimensionado para milhares de milhões de pessoas e grupos de amigos.