Disjoint Set (Union-Find Algorithm) PHP:ssä

Julkaistu: 16. helmikuuta 2025 klo 12.25.16 UTC
Viimeksi päivitetty: 26. tammikuuta 2026 klo 10.36.45 UTC

Tässä artikkelissa esitellään PHP-toteutus Disjoint Set -tietorakenteelle, jota yleisesti käytetään Union-Find -algoritmeissa minimispanning tree -algoritmeissa.

Tämä sivu on käännetty koneellisesti englannista, jotta se olisi mahdollisimman monen ihmisen saatavilla. Valitettavasti konekääntäminen ei ole vielä täydellistä tekniikkaa, joten virheitä voi esiintyä. Voit halutessasi tarkastella alkuperäistä englanninkielistä versiota täällä:

Disjoint Set (Union-Find Algorithm) in PHP

Erillinen joukko (yleisesti käytetty Union-Find eli Disjoint Set Union) on tietorakenne, jota käytetään alkioiden jakamisen hallintaan erillisiksi (ei-päällekkäisiksi) joukoiksi. Se tukee kahta keskeistä toimintoa tehokkaasti:

Löydä: Määrittää, mihin joukkoon alkio kuuluu.
Union: Yhdistää kaksi joukkoa.

Tämä rakenne on erityisen hyödyllinen minimispanning tree -algoritmeissa, kuten Kruskalin algoritmissa.

Minulla on Kruskalin algoritmin toteutus, jota käytetään satunnaisten labyrinttien luomiseen ja joka perustuu alla olevaan Disjoint Set -PHP-toteutukseen settien tehokkaaseen yhdistämiseen. Jos olet kiinnostunut, voit nähdä sen toiminnassa täällä: Kruskalin algoritmi sokkelogeneraattori

Joka tapauksessa, tässä on PHP-toteutukseni Disjoint Setistä:

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

Labyrinttien luomisen lisäksi Disjoint Set -tietorakennetta voidaan varmasti käyttää myös todellisissa tilanteissa.

Kuvittele esimerkiksi sosiaalinen verkosto, joka haluaisi ehdottaa käyttäjilleen uusia ystäviä, ja sanotaan, että meillä on jo kuusi ihmistä, joilla on nämä ystäväsuhteet:

1 ja 2 ovat ystäviä.
2 ja 3 ovat ystäviä.
4 ja 5 ovat ystäviä.
6:lla ei ole ystäviä.

Soveltamalla Union-Find-algoritmia näihin erillisiin ryhmiin, löydetään seuraavat:

1, 2 ja 3 samassa ryhmässä.
4 ja 5 toisessa ryhmässä.
6 kolmannessa ryhmässä.

Tämän perusteella olisi järkevää ehdottaa, että 1 ja 3 ystävystyisivät, koska heillä on yhteinen henkilö 2.

Tietenkin pienessä esimerkissä kuten tämä voisi helposti huomata tämän itse, mutta tämän algoritmin tehokkuus mahdollistaa sen järkevän skaalautumisen miljardeille ihmisille ja kaveriporukoille.