Insieme disgiunto (algoritmo Union-Find) in PHP

Pubblicato: 16 febbraio 2025 alle ore 12:25:42 UTC
Ultimo aggiornamento: 26 gennaio 2026 alle ore 10:36:50 UTC

Questo articolo presenta un'implementazione PHP della struttura dati Disjoint Set, comunemente utilizzata per Union-Find negli algoritmi ad albero di riduzione minima.

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 noto anche come Disjoint Set Union) è una struttura dati utilizzata per gestire una partizione di elementi in insiemi disgiunti (non sovrapposti). Supporta in modo efficiente due operazioni chiave:

Trova: Determina a quale insieme appartiene un elemento.
Unione: Unisce due set.

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

Ho un'implementazione dell'algoritmo di Kruskal usata per generare labirinti casuali che si basa sull'implementazione in PHP di Disjoint Set che segue per unire insiemi in modo efficiente. Se ti interessa, 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 reali.

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

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 una persona 2 in comune.

Certo, in un piccolo esempio come questo, potresti facilmente individuare questo fatto da solo, ma l'efficienza di questo algoritmo gli permette di scalare fattibilmente a miliardi di persone e gruppi di amici.