Conjunto Disjunto (Union-Find Algorithm) em PHP

Publicado: 16 de fevereiro de 2025 às 12:26:46 UTC
Última atualização: 26 de janeiro de 2026 às 10:36:56 UTC

Este artigo apresenta uma implementação PHP da estrutura de dados Disjoint Set, comumente usada para Union-Find em algoritmos de árvore de expansã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 Conjunto Disconjunto (comumente usado para Union-Finch, também conhecido como União de Conjuntos Disjuntos) é uma estrutura de dados usada para gerir uma partição de elementos em conjuntos disjuntos (não sobrepostos). Suporta duas operações-chave de forma eficiente:

Encontrar: Determina a que conjunto pertence um elemento.
União: Funde dois conjuntos.

Esta estrutura é particularmente útil em algoritmos de árvore geradora mínima, como o algoritmo de Kruskal.

Tenho uma implementação do algoritmo de Kruskal usada para gerar labirintos aleatórios que se baseia na implementação PHP abaixo do Disjoint Set para fundir conjuntos de forma eficiente. Se estiveres interessado, podes 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]++;
            }
        }
    }
}

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

Imagine, por exemplo, uma rede social que gostaria de sugerir novos amigos aos seus utilizadores, e depois digamos que temos seis pessoas com essas relações de amizade já existentes:

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

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

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

Com base nisto, faria sentido sugerir que o 1 e o 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 próprio, mas a eficiência deste algoritmo permite que escale de forma viável para milhares de milhões de pessoas e grupos de amigos.