Disjoint Set (Union-Find Algorithm) a CIKINMÃNI

Buga: 16 Faburairu, 2025 da 12:29:31 UTC

Wannan talifin yana ɗauke da yadda aka yi amfani da tsarin bayani na Disjoint Set, wanda ake amfani da shi a union-Find a ƙanƙanin hanyoyin aiki na itace.

An fassara wannan shafin na'ura daga Turanci don a sami damar isa ga mutane da yawa gwargwadon iko. Abin takaici, fassarar inji ba ta zama cikakkiyar fasaha ba, don haka kurakurai na iya faruwa. Idan kuna so, kuna iya duba ainihin sigar Turanci anan:

Disjoint Set (Union-Find Algorithm) in PHP

Shirin Disjoint (da ake amfani da shi a yau don Union-Find a.k.a. Disjoint Set Union) tsarin bayani ne da ake amfani da shi don kula da raba abubuwa cikin shiryoyin da ba su da haɗin kai (ba su daidaita ba). Yana goyon bayan aiki biyu masu muhimmanci da kyau:

Ka sami: Ka san wanda ya sa wani abu ya zama na.
Haɗin kai: Ya haɗa rukuni biyu tare.

Wannan tsarin yana da amfani musamman a ƙanƙantar algorithms na itace, kamar algorithm na Kruskal.

Ina da aiwatar da algorithm na Kruskal da aka yi amfani da shi don samar da abubuwan da ba su dace ba wanda ya dogara ne akan aiwatar da tsarin DISjoint don haɗa nau'i-nau'i. Idan kana son, za ka iya ganin shi a aiki a nan: Kruskal na Algorithm Maze Generator

Ko kaɗan, wannan shi ne aikin DA NA NA NA

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

Ban da halittar ƙanƙara don jin daɗi, za a iya yin amfani da tsarin bayani na Disjoint Set don yanayi na rayuwa na gaske.

Alal misali, ka yi tunanin wani dandalin sada zumunta da zai so ya gaya wa sababbin abokai ga waɗanda suke amfani da shi, kuma bari mu ce muna da mutane shida da suke da waɗannan dangantakar abokai da suka riga sun yi:

1 da 2 abokai ne.
2 da 3 abokai ne.
4 da 5 abokai ne.
6 Ba shi da abokai.

Idan muka yi amfani da tsarin aiki na Union-Find ga waɗannan rukunoni dabam dabam, ya kamata mu samu waɗannan:

1, 2 da 3 a rukuni ɗaya.
4 da 5 a rukuni na biyu.
6 a rukuni na uku.

Bisa ga wannan, zai dace a ce mutum ɗaya da uku su zama abokai, domin suna da mutum biyu da suke kama da juna.

Hakika, a ƙaramin misali kamar wannan, za ka iya ganin wannan gaskiyar da kanka, amma yadda wannan tsarin yake aiki ya sa ya yiwu ya kai biliyoyin mutane da rukunonin abokai.