Set disjunc (Algoritmul Union-Find) în PHP
Publicat: 16 februarie 2025 la 12:26:52 UTC
Acest articol prezintă o implementare PHP a structurii de date Disjoint Set, folosită în mod obișnuit pentru Union-Find în algoritmi de arbore de acoperire minim.
Disjoint Set (Union-Find Algorithm) in PHP
Setul Disjoint (utilizat în mod obișnuit pentru Union-Find, alias Disjoint Set Union) este o structură de date folosită pentru a gestiona o partiție a elementelor în seturi disjunse (nesuprapuse). Acceptă două operațiuni cheie în mod eficient:
- Găsire : Stabilește cărei mulțime îi aparține un element.
- Unire : Unește două seturi împreună.
Această structură este deosebit de utilă în algoritmii arborelui de acoperire minimă, cum ar fi algoritmul lui Kruskal.
Am o implementare a algoritmului lui Kruskal folosit pentru generarea de labirinturi aleatoare care se bazează pe implementarea PHP de mai jos a Disjoint Set pentru a îmbina eficient seturile. Dacă ești interesat, îl poți vedea în acțiune aici: Generatorul de labirint al algoritmului lui Kruskal
Oricum, aceasta este implementarea mea PHP a 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]++;
}
}
}
}
Pe lângă generarea de labirinturi pentru distracție, structura de date Disjoint Set poate fi folosită cu siguranță și pentru scenarii din viața reală.
Imaginați-vă, de exemplu, o rețea de socializare care ar dori să sugereze noi prieteni utilizatorilor săi și apoi să spunem că avem șase persoane cu aceste relații de prieteni deja existente:
- 1 și 2 sunt prieteni.
- 2 și 3 sunt prieteni.
- 4 și 5 sunt prieteni.
- 6 nu are prieteni.
Aplicând algoritmul Union-Find acestor grupuri separate, ar trebui să găsim următoarele:
- 1, 2 și 3 într-un singur grup.
- 4 și 5 într-o a doua grupă.
- 6 într-un al treilea grup.
Pe baza acestui lucru, ar avea sens să sugerăm că 1 și 3 ar trebui să devină prieteni, deoarece au persoana 2 în comun.
Desigur, într-un mic exemplu ca acesta, ați putea observa cu ușurință acest fapt, dar eficiența acestui algoritm îi permite să se extindă fezabil la miliarde de oameni și grupuri de prieteni.