Disjoint Set (Union-Find Algorithm) sa PHP

Nai-publish: Marso 19, 2025 nang 9:36:33 PM UTC

Nagtatampok ang artikulong ito ng pagpapatupad ng PHP ng istruktura ng data ng Disjoint Set, na karaniwang ginagamit para sa Union-Find sa pinakamababang spanning tree algorithm.

Ang pahinang ito ay isinalin sa makina mula sa Ingles upang gawin itong naa-access sa pinakamaraming tao hangga't maaari. Sa kasamaang palad, ang pagsasalin ng makina ay hindi pa isang perpektong teknolohiya, kaya maaaring mangyari ang mga error. Kung gusto mo, maaari mong tingnan ang orihinal na bersyong Ingles dito:

Disjoint Set (Union-Find Algorithm) in PHP

Ang Disjoint Set (karaniwang ginagamit para sa Union-Find o Disjoint Set Union) ay isang istruktura ng datos na ginagamit upang pamahalaan ang paghahati ng mga elemento sa mga disjoint (hindi nag-o-overlap) na set. Ito ay sumusuporta sa dalawang pangunahing operasyon ng mahusay:

Find: Tinutukoy kung aling set ang kinabibilangan ng isang elemento.
Union: Pinagsasama ang dalawang set.

Ang istruktura na ito ay partikular na kapaki-pakinabang sa mga algorithm ng minimum spanning tree, tulad ng Kruskal's algorithm.

Mayroon akong isang implementasyon ng Kruskal's algorithm na ginagamit para sa pag-generate ng mga random na labirinto na umaasa sa ibaba na PHP implementasyon ng Disjoint Set upang mahusay na pagsamahin ang mga set. Kung interesado ka, maaari mo itong makita sa aksyon dito: Ang Algorithm Maze Generator ng Kruskal

Gayunpaman, ito ang aking PHP implementasyon ng 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]++;
            }
        }
    }
}

Bukod sa pag-generate ng mga labirinto para sa kasiyahan, ang Disjoint Set data structure ay tiyak na magagamit din para sa mga tunay na sitwasyon sa buhay.

Isipin, halimbawa, isang social network na nais magmungkahi ng mga bagong kaibigan sa mga gumagamit nito, at sabihin na mayroon tayong anim na tao na may mga relasyon ng pagkakaibigan na nakatala na:

1 at 2 ay magkaibigan.
2 at 3 ay magkaibigan.
4 at 5 ay magkaibigan.
6 ay walang kaibigan.

Sa paggamit ng Union-Find algorithm sa mga hiwalay na grupong ito, dapat nating makita ang mga sumusunod:

1, 2 at 3 sa isang grupo.
4 at 5 sa pangalawang grupo.
6 sa pangatlong grupo.

Batay dito, makatarungan na magmungkahi na si 1 at 3 ay dapat maging magkaibigan, dahil mayroon silang taong 2 na karaniwan.

Siyempre, sa isang maliit na halimbawa tulad nito, maaari mo itong makita ng madali, ngunit ang kahusayan ng algorithm na ito ay nagpapahintulot dito upang mag-scale sa bilyun-bilyong tao at mga grupo ng kaibigan.