Insieme disgiunto (algoritmo Union-Find) in PHP

Pubblicato: 16 febbraio 2025 alle ore 12:25:42 UTC

Questo articolo presenta un'implementazione PHP della struttura dati Disjoint Set, comunemente utilizzata per Union-Find negli algoritmi di minimum spanning tree.

Questa pagina è stata tradotta automaticamente dall'inglese per renderla accessibile al maggior numero di persone possibile. Purtroppo, la traduzione automatica non è ancora una tecnologia perfezionata, quindi possono verificarsi degli errori. Se preferite, potete consultare la versione originale in inglese qui:

Disjoint Set (Union-Find Algorithm) in PHP

Il Disjoint Set (comunemente usato per Union-Find, ovvero Disjoint Set Union) è una struttura dati usata per gestire una partizione di elementi in set disgiunti (non sovrapposti). Supporta due operazioni chiave in modo efficiente:

Trova : determina a quale insieme appartiene un elemento.
Unione : unisce due insiemi.

Questa struttura è particolarmente utile negli algoritmi di albero di copertura minimo, come l'algoritmo di Kruskal.

Ho un'implementazione dell'algoritmo di Kruskal utilizzato per generare labirinti casuali che si basa sull'implementazione PHP sottostante di Disjoint Set per unire in modo efficiente i set. Se sei interessato, puoi vederlo in azione qui: Generatore di labirinti con algoritmo di Kruskal

Comunque, questa è la mia implementazione PHP di 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]++;
            }
        }
    }
}

Oltre a generare labirinti per divertimento, la struttura dati Disjoint Set può certamente essere utilizzata anche per scenari di vita reale.

Immaginiamo, ad esempio, un social network che vorrebbe suggerire nuovi amici ai suoi utenti e poi supponiamo di avere sei persone con queste relazioni di amicizia già attive:

1 e 2 sono amici.
2 e 3 sono amici.
4 e 5 sono amici.
6 non ha amici.

Applicando l'algoritmo Union-Find a questi gruppi separati, dovremmo trovare quanto segue:

1, 2 e 3 in un gruppo.
4 e 5 in un secondo gruppo.
6 in un terzo gruppo.

Sulla base di ciò, avrebbe senso suggerire che 1 e 3 diventino amici, perché hanno la persona 2 in comune.

Naturalmente, in un piccolo esempio come questo, potresti facilmente individuare questo fatto da solo, ma l'efficienza di questo algoritmo gli consente di essere facilmente esteso a miliardi di persone e gruppi di amici.