Disjoint Set (Union-Find Algorithm) PHP
Publicēts: 2025. gada 16. februāris 12:26:08 UTC
Šajā rakstā ir ietverta PHP implementācija Disjoint Set datu struktūrai, ko parasti izmanto Union-Find minimālo aptverošo koku algoritmos.
Disjoint Set (Union-Find Algorithm) in PHP
Disjoint Set (ko parasti izmanto Union-Find jeb Disjoint Set Union) ir datu struktūra, ko izmanto, lai pārvaldītu elementu nodalījumu nesadalītās (nepārklājas) kopās. Tas efektīvi atbalsta divas galvenās darbības:
- Find : nosaka, kurai kopai pieder elements.
- Savienība : apvieno divas kopas.
Šī struktūra ir īpaši noderīga minimālo aptverošo koku algoritmos, piemēram, Kruskal algoritmā.
Man ir Kruskal algoritma implementācija, ko izmanto nejaušu labirintu ģenerēšanai, kas balstās uz tālāk norādīto PHP Disjoint Set implementāciju, lai efektīvi apvienotu kopas. Ja jūs interesē, jūs varat redzēt to darbībā šeit: Kruskal algoritma labirinta ģenerators
Jebkurā gadījumā šī ir mana Disjoint Set PHP ieviešana:
{
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]++;
}
}
}
}
Papildus labirintu ģenerēšanai izklaidei, Disjoint Set datu struktūru noteikti var izmantot arī reālās dzīves scenārijiem.
Iedomājieties, piemēram, sociālo tīklu, kas vēlas saviem lietotājiem ieteikt jaunus draugus, un tad pieņemsim, ka mums ir seši cilvēki, kuriem jau ir izveidotas šādas draugu attiecības:
- 1 un 2 ir draugi.
- 2 un 3 ir draugi.
- 4 un 5 ir draugi.
- 6 nav draugu.
Izmantojot Union-Find algoritmu šīm atsevišķajām grupām, mums vajadzētu atrast sekojošo:
- 1, 2 un 3 vienā grupā.
- 4 un 5 otrajā grupā.
- 6 trešajā grupā.
Pamatojoties uz to, būtu lietderīgi ieteikt 1. un 3. kļūt par draugiem, jo viņiem ir kopīgs 2. cilvēks.
Protams, šādā nelielā piemērā jūs pats varētu viegli pamanīt šo faktu, taču šī algoritma efektivitāte ļauj to mērogot līdz miljardiem cilvēku un draugu grupām.