Miklix

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.


Această pagină a fost tradusă automat din limba engleză pentru a o face accesibilă cât mai multor persoane. Din păcate, traducerea automată nu este încă o tehnologie perfecționată, astfel încât pot apărea erori. Dacă preferați, puteți vizualiza versiunea originală în limba engleză aici:

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:

  1. Găsire : Stabilește cărei mulțime îi aparține un element.
  2. 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:

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]++;
            }
        }
    }
}

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.

Distribuie pe BlueskyDistribuie pe FacebookDistribuie pe LinkedInDistribuie pe TumblrDistribuie pe XDistribuie pe LinkedInPin pe Pinterest

Mikkel Bang Christensen

Despre autor

Mikkel Bang Christensen
Mikkel este creatorul și proprietarul miklix.com. El are peste 20 de ani de experiență ca programator de calculatoare/dezvoltator software profesionist și este în prezent angajat cu normă întreagă pentru o mare corporație europeană de IT. Atunci când nu scrie pe blog, își petrece timpul liber cu o gamă largă de interese, hobby-uri și activități, care se pot reflecta într-o anumită măsură în varietatea de subiecte abordate pe acest site.