Disjoint Set (Union-Find Algorithm) í PHP

Birt: 19. mars 2025 kl. 21:36:29 UTC

Þessi grein inniheldur PHP útfærslu á Disjoint Set gagnaskipulaginu, sem almennt er notað fyrir Union-Find í reikniritum fyrir lágmarksspennandi tré.

Þessi síða var vélþýdd úr ensku til að gera hana aðgengilega sem flestum. Því miður er vélþýðing ekki enn fullkomin tækni, svo villur geta komið upp. Ef þú vilt geturðu skoðað upprunalegu ensku útgáfuna hér:

Disjoint Set (Union-Find Algorithm) in PHP

Disjoint Set (oft notað fyrir Union-Find eða Disjoint Set Union) er gagnagerð sem notuð er til að stjórna skiptingu elemennta í sundurstaðna (óviðkomandi) mengi. Hún styður tvær lykil aðgerðir á áhrifaríkan hátt:

Find: Ákveður í hvaða mengi element tilheyrir.
Union: Sameinar tvö mengi saman.

Þessi uppbygging er sérstaklega gagnleg í reikniritum fyrir minnsta tengingu tré, eins og Kruskal reikniritinu.

Ég hef útfærslu á Kruskal reikniritinu sem notað er til að búa til handahófskennda völundarhús og byggir á eftirfarandi PHP útfærslu af Disjoint Set til að sameina mengi á áhrifaríkan hátt. Ef þú ert áhugasamur, getur þú séð það í notkun hér: Kruskal's Algoritma Maze Generator

Allavega, þetta er mín PHP útfærsla af 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]++;
            }
        }
    }
}

Auk þess að búa til völundarhús fyrir gaman, getur Disjoint Set gagnagerðin vissulega einnig verið notuð í raunverulegum aðstæðum.

Ímyndaðu þér, til dæmis, samfélagsnet sem vill leggja til nýja vini fyrir notendur sína, og við skulum segja að við höfum sex manneskjur með þessi vinatengsl þegar þau eru þegar til staðar:

1 og 2 eru vinir.
2 og 3 eru vinir.
4 og 5 eru vinir.
6 hefur enga vini.

Með því að beita Union-Find reikniritinu á þessa aðskilda hópa ættum við að finna eftirfarandi:

1, 2 og 3 í einum hóp.
4 og 5 í öðrum hóp.
6 í þriðja hópnum.

Byggt á þessu, myndi það vera skiljanlegt að leggja til að 1 og 3 ættu að verða vinir, vegna þess að þau hafa manneskju 2 sameiginlega.

Að sjálfsögðu, í svona litlu dæmi, gætir þú auðveldlega séð þessa staðreynd sjálfur, en skilvirkni þessa reiknirit leyfir því að skalast með raunverulegum hætti upp í milljarða manna og vinahópa.