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.
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:
{
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.