Disjoint Set (Union-Find Algorithm) dina PHP

Diterbitkeun: 16 Pébruari 2025 jam 12.33.37 UTC

Tulisan ieu ngagaduhan palaksanaan PHP tina struktur data Disjoint Set, anu biasa dianggo pikeun Union-Find dina algoritma tangkal bentang minimum.

Kaca ieu ditarjamahkeun ku mesin tina basa Inggris supados tiasa diaksés ku saloba-lobana jalma. Hanjakalna, tarjamahan mesin henteu acan janten téknologi anu sampurna, janten kasalahan tiasa lumangsung. Upami anjeun hoyong, anjeun tiasa ningali versi Inggris asli di dieu:

Disjoint Set (Union-Find Algorithm) in PHP

The Disjoint Set (umumna dipaké pikeun Union-Find alias Disjoint Set Union) nyaéta struktur data anu dipaké pikeun ngatur partisi elemen kana susunan disjoint (non-tumpang tindih). Ieu ngarojong dua operasi konci éfisién:

Pilarian : Nangtukeun mana set hiji unsur milik.
Uni : Ngagabung dua set babarengan.

Struktur ieu hususna kapaké dina algoritma tangkal bentang minimum, sapertos algoritma Kruskal.

Kuring boga hiji palaksanaan algoritma Kruskal urang dipaké pikeun generating mazes acak nu ngandelkeun palaksanaan handap PHP of Disjoint Set pikeun éfisién ngagabungkeun susunan. Upami anjeun kabetot, anjeun tiasa ningali tindakanna di dieu: Kruskal urang Algoritma Maze generator

Atoh, ieu mangrupikeun palaksanaan PHP kuring tina 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]++;
            }
        }
    }
}

Salian ti ngahasilkeun mazes pikeun senang, struktur data Disjoint Set pasti ogé bisa dipaké pikeun skenario real-life.

Bayangkeun, contona, jaringan sosial anu hoyong nyarankeun réréncangan énggal ka pangguna, teras anggap yén urang ngagaduhan genep jalma anu ngagaduhan hubungan réréncangan ieu:

1 jeung 2 babaturan.
2 jeung 3 babaturan.
4 jeung 5 babaturan.
6 teu boga babaturan.

Nerapkeun algoritma Union-Find ka grup anu misah ieu, urang kedah mendakan ieu:

1, 2 jeung 3 dina hiji grup.
4 jeung 5 dina grup kadua.
6 dina grup katilu.

Dumasar ieu, éta bakal asup akal pikeun nyarankeun yén 1 jeung 3 kudu jadi babaturan, sabab boga jalma 2 di umum.

Tangtosna, dina conto alit sapertos kieu, anjeun tiasa terang kanyataan ieu nyalira, tapi efisiensi algoritma ieu ngamungkinkeun pikeun skala pikeun milyaran jalma sareng grup babaturan.