Seti ya Kuunganishwa (Union-Find Algorithm) katika PHP

Iliyochapishwa: 16 Februari 2025, 12:28:51 UTC

Makala hii ina utekelezaji wa PHP wa muundo wa data ya Disjoint Seti, ambayo hutumiwa kwa Umoja-Find katika algorithms ya chini ya miti.

Ukurasa huu ulitafsiriwa kwa mashine kutoka kwa Kiingereza ili kuifanya iweze kupatikana kwa watu wengi iwezekanavyo. Kwa bahati mbaya, utafsiri wa mashine bado sio teknolojia iliyokamilishwa, kwa hivyo makosa yanaweza kutokea. Ukipenda, unaweza kutazama toleo asili la Kiingereza hapa:

Disjoint Set (Union-Find Algorithm) in PHP

Seti ya Disjoint (inayotumiwa kwa kawaida kwa Union-Find a.k.a. Disjoint Set Union) ni muundo wa data unaotumiwa kusimamia kizigeu cha vipengele katika seti za disjoint (zisizo za juu). Inasaidia shughuli mbili muhimu kwa ufanisi:

Tafuta: Huamua ni seti gani ya kipengele ni ya.
Umoja: Inaunganisha seti mbili pamoja.

Muundo huu ni muhimu sana katika algorithms ya chini ya miti, kama vile algorithm ya Kruskal.

Nina utekelezaji wa algorithm ya Kruskal inayotumiwa kwa kuzalisha mazes ya random ambayo inategemea utekelezaji wa PHP chini ya Seti ya Disjoint ili kuunganisha seti kwa ufanisi. Ikiwa una nia, unaweza kuiona kwa vitendo hapa: Jenereta ya Maze ya Algorithm ya Kruskal

Kwa hivyo, hii ni utekelezaji wangu wa PHP wa Seti ya Disjoint:

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

Mbali na kuzalisha mazes kwa ajili ya kujifurahisha, Disjoint Set data muundo inaweza pia kutumika kwa ajili ya matukio halisi ya maisha.

Fikiria, kwa mfano, mtandao wa kijamii ambao ungependa kupendekeza marafiki wapya kwa watumiaji wake, na kisha wacha tuseme kwamba tuna watu sita wenye uhusiano huu wa rafiki tayari mahali:

1 na 2 ni marafiki.
2 na 3 ni marafiki.
4 na 5 ni marafiki.
6 Hakuna rafiki.

Kutumia algorithm ya Umoja-Find kwa vikundi hivi tofauti, tunapaswa kupata yafuatayo:

1, 2 na 3 katika kundi moja.
4 na 5 katika kundi la pili.
6 katika kundi la tatu.

Kulingana na hili, itakuwa na maana kupendekeza kwamba 1 na 3 inapaswa kuwa marafiki, kwa sababu wana mtu 2 kwa kawaida.

Bila shaka, katika mfano mdogo kama huu, unaweza kuona ukweli huu mwenyewe, lakini ufanisi wa algorithm hii inaruhusu kwa kiwango kikubwa kwa mabilioni ya watu na vikundi vya marafiki.