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

Buga: 16 Faburairu, 2025 da 12:29:31 UTC
An sabunta ta ƙarshe: 26 Janairu, 2026 da 10:37:07 UTC

Wannan labarin ya ƙunshi aiwatar da PHP na tsarin bayanan Disjoint Set, wanda aka saba amfani dashi don Union-Find a cikin mafi ƙarancin algorithms 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

Saitin Disjoint (wanda aka saba amfani dashi don Union-Find aka Disjoint Set Union) tsari ne na bayanai da aka yi amfani da shi don sarrafa ɓangaren abubuwa a cikin rarrabuwa (wanda ba a haɗa shi ba). Yana goyon bayan biyu key ayyuka yadda ya kamata:

Nemo: Ƙayyade wane saitin wani abu ya kasance.
Union: Merges biyu sets tare.

Wannan tsarin yana da amfani musamman a cikin mafi ƙarancin algorithms na itace, kamar algorithm na Kruskal.

Ina da aiwatar da algorithm na Kruskal da aka yi amfani da shi don samar da bazuwar mazes wanda ya dogara da aiwatar da PHP da ke ƙasa na Disjoint Set don haɗa saiti yadda ya kamata. Idan kuna sha'awar, zaku iya ganin shi a cikin aiki a nan: Kruskal na Algorithm Maze Generator

Ko ta yaya, wannan shine PHP na aiwatar da 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]++;
            }
        }
    }
}

Baya ga samar da mazes don nishaɗi, ana iya amfani da tsarin bayanan Disjoint Set don al'amuran rayuwa na ainihi.

Ka yi tunani, alal misali, hanyar sadarwar zamantakewa wacce ke son ba da shawarar sababbin abokai ga masu amfani da ita, sannan kuma bari mu ce muna da mutane shida tare da waɗannan alaƙar abokai da suka riga sun kasance a wurin:

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

Yin amfani da algorithm na Union-Find zuwa waɗannan ƙungiyoyi daban-daban, ya kamata mu sami waɗannan:

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

Dangane da wannan, zai zama ma'ana a ba da shawarar cewa 1 da 3 ya kamata su zama abokai, saboda suna da mutum 2 a cikin kowa.

Tabbas, a cikin ƙaramin misali kamar wannan, zaku iya hango wannan gaskiyar da kanku, amma ingancin wannan algorithm yana ba shi damar haɓaka zuwa biliyoyin mutane da ƙungiyoyin abokai.