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

Julkaistu: 16. helmikuuta 2025 klo 12.25.16 UTC

Tässä artikkelissa on PHP-toteutus Disjoint Set -tietorakenteelle, jota käytetään yleisesti Union-Findissä minimivirittävän puun 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

Disjoint Set (käytetään yleisesti Union-Findille eli Disjoint Set Unionille) on tietorakenne, jota käytetään elementtien osion hallintaan hajautetuiksi (ei-päällekkäisiksi) joukoiksi. Se tukee kahta avaintoimintoa tehokkaasti:

Etsi : Määrittää, mihin joukkoon elementti kuuluu.
Unioni : Yhdistää kaksi sarjaa yhteen.

Tämä rakenne on erityisen hyödyllinen minimivirittävän puun algoritmeissa, kuten Kruskalin algoritmissa.

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

Joka tapauksessa tämä on minun 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]++;
            }
        }
    }
}

Sen lisäksi, että luodaan sokkeloita huvin vuoksi, Disjoint Set -tietorakennetta voidaan varmasti käyttää myös tosielämän skenaarioissa.

Kuvittele esimerkiksi sosiaalinen verkosto, joka haluaisi ehdottaa uusia ystäviä käyttäjilleen, ja sitten oletetaan, että meillä on kuusi henkilöä, joilla on jo 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ä.

Kun sovelletaan Union-Find-algoritmia näihin erillisiin ryhmiin, meidän pitäisi löytää seuraava:

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

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

Tietysti tällaisessa pienessä esimerkissä voit helposti havaita tämän tosiasian itse, mutta tämän algoritmin tehokkuus mahdollistaa sen, että se skaalautuu miljardeihin ihmisiin ja ystäväryhmiin.