Conjunto Disjunto (Algoritmo Union-Find) em PHP

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

Este artigo apresenta uma implementação PHP da estrutura de dados Disjoint Set, comumente usada para Union-Find em algoritmos de árvore de extensã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 Disjoint Set (comumente usado para Union-Find, também conhecido como Disjoint Set Union) é uma estrutura de dados usada para gerenciar uma partição de elementos em conjuntos disjuntos (não sobrepostos). Ele suporta duas operações principais de forma eficiente:

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

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

Eu tenho uma implementação do algoritmo de Kruskal usado para gerar labirintos aleatórios que depende da implementação PHP abaixo de Disjoint Set para mesclar conjuntos de forma eficiente. Se você estiver interessado, pode vê-lo em ação aqui: Gerador de labirintos do algoritmo de Kruskal

De qualquer forma, 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 temos seis pessoas com esses relacionamentos de amizade já estabelecidos:

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 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 1 e 3 se tornassem amigos, porque eles têm a pessoa 2 em comum.

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