Conjunto Disjunto (Algoritmo Union-Find) em PHP

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

Este artigo apresenta uma implementação em 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 torná-la acessível ao maior número possível de pessoas. Infelizmente, a tradução automática ainda não é uma tecnologia aperfeiçoada, portanto, podem ocorrer erros. Se preferir, você pode visualizar 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 gerenciar uma partição de elementos em conjuntos disjuntos (não sobrepostos). Ele suporta duas operações-chave de forma eficiente:

Encontrar: Determina a qual conjunto um elemento pertence.
União: Une dois conjuntos.

Essa 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 depende da implementação em PHP abaixo do Disjoint Set para mesclar conjuntos de forma eficiente. Se você se interessar, pode ver isso em ação aqui: Gerador de labirintos do algoritmo de Kruskal

Enfim, esta é 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 certamente também pode ser usada em cenários da vida real.

Imagine, por exemplo, uma rede social que gostaria de sugerir novos amigos para seus usuários, e então digamos que já temos seis pessoas com esses relacionamentos de amizade estabelecidos:

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

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

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

Com base nisso, faria sentido sugerir que o 1 e o 3 se tornem amigos, porque eles têm a pessoa 2 em comum.

Claro, em um exemplo pequeno como esse, você poderia facilmente perceber esse fato, mas a eficiência desse algoritmo permite que ele escale para bilhões de pessoas e grupos de amigos.