Disjoint Set (Union-Find Algorithm) i PHP
Publicerad: 16 februari 2025 kl. 12:27:23 UTC
Den här artikeln innehåller en PHP-implementering av datastrukturen Disjoint Set, som vanligen används för Union-Find i algoritmer för minimum spaning tree.
Disjoint Set (Union-Find Algorithm) in PHP
Disjoint Set (används vanligen för Union-Find aka Disjoint Set Union) är en datastruktur som används för att hantera en partition av element i disjunta (icke-överlappande) uppsättningar. Den stöder två nyckeloperationer effektivt:
- Hitta : Bestämmer vilken uppsättning ett element tillhör.
- Union : Slår samman två uppsättningar.
Den här strukturen är särskilt användbar i algoritmer med minsta spännträd, såsom Kruskals algoritm.
Jag har en implementering av Kruskals algoritm som används för att generera slumpmässiga labyrinter som förlitar sig på nedanstående PHP-implementering av Disjoint Set för att effektivt slå samman set. Om du är intresserad kan du se den i aktion här: Kruskals algoritm labyrintgenerator
Hur som helst, detta är min PHP-implementering av 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]++;
}
}
}
}
Förutom att generera labyrinter för skojs skull kan Disjoint Set-datastrukturen säkert också användas för verkliga scenarier.
Föreställ dig till exempel ett socialt nätverk som skulle vilja föreslå nya vänner till sina användare, och låt oss sedan säga att vi har sex personer med dessa vänrelationer redan på plats:
- 1 och 2 är vänner.
- 2 och 3 är vänner.
- 4 och 5 är vänner.
- 6 har inga vänner.
Genom att tillämpa Union-Find-algoritmen på dessa separata grupper bör vi hitta följande:
- 1, 2 och 3 i en grupp.
- 4 och 5 i en andra grupp.
- 6 i en tredje grupp.
Utifrån detta skulle det vara vettigt att föreslå att 1 och 3 ska bli vänner, eftersom de har person 2 gemensamt.
Naturligtvis, i ett litet exempel som detta, kan du enkelt upptäcka detta faktum själv, men effektiviteten hos denna algoritm gör att den kan skalas till miljarder människor och vängrupper.