Seti ya Kuunganishwa (Union-Find Algorithm) katika PHP

Iliyochapishwa: 16 Februari 2025, 12:28:51 UTC
Mara ya mwisho kusasishwa: 26 Januari 2026, 10:37:04 UTC

Makala haya yanaangazia utekelezaji wa PHP wa muundo wa data wa Disjoint Set, unaotumiwa sana kwa Union-Find katika kanuni za chini zaidi za 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 sana kwa Union-Find aka Disjoint Set Union) ni muundo wa data unaotumiwa kudhibiti kizigeu cha vipengele katika seti zisizounganishwa (zisizoingiliana). Inasaidia shughuli mbili muhimu kwa ufanisi:

Tafuta: Huamua ni seti gani ya kipengele.
Muungano: 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 kutengeneza maze bila mpangilio ambayo inategemea utekelezaji wa PHP ulio hapa chini wa Seti ya Disjoint ili kuunganisha seti kwa ufanisi. Ikiwa una nia, unaweza kuiona ikifanya kazi hapa: Jenereta ya Maze ya Algorithm ya Kruskal

Kwa hivyo, huu 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]++;
            }
        }
    }
}

Kando na kuzalisha mazes kwa ajili ya kujifurahisha, muundo wa data wa Disjoint Set unaweza pia kutumika kwa matukio halisi ya maisha.

Hebu fikiria, kwa mfano, mtandao wa kijamii ambao ungependa kupendekeza marafiki wapya kwa watumiaji wake, na kisha tuseme kwamba tuna watu sita walio na mahusiano haya ya marafiki tayari:

1 na 2 ni marafiki.
2 na 3 ni marafiki.
4 na 5 ni marafiki.
6 haina marafiki.

Kutumia algorithm ya Muungano-Tafuta kwa vikundi hivi tofauti, tunapaswa kupata yafuatayo:

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

Kulingana na hili, itakuwa na maana kupendekeza kwamba 1 na 3 wanapaswa kuwa marafiki, kwa sababu wana mtu wa 2 sawa.

Kwa kweli, kwa mfano mdogo kama huu, unaweza kuona ukweli huu mwenyewe kwa urahisi, lakini ufanisi wa algorithm hii inaruhusu kuongezeka kwa mabilioni ya watu na vikundi vya marafiki.