Disjoint Set (Union-Find Algorithm) dina PHP

Diterbitkeun: 16 Pébruari 2025 jam 12.33.37 UTC
Panungtungan diropéa: 26 Januari 2026 jam 10.37.15 UTC

Artikel ieu nampilkeun implementasi PHP tina struktur data Disjoint Set, anu umumna dianggo pikeun Union-Find dina algoritma tangkal rentang 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

Set Disjoint (anu umumna dianggo pikeun Union-Find alias Disjoint Set Union) nyaéta struktur data anu dianggo pikeun ngatur partisi unsur kana set anu teu silih tumpang tindih (henteu tumpang tindih). Éta ngadukung dua operasi konci sacara efisien:

Find : Nangtukeun kagolong kana himpunan mana hiji unsur.
Gabungan : Ngahijikeun dua himpunan.

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

Abdi gaduh implementasi algoritma Kruskal anu dianggo pikeun ngahasilkeun labirin acak anu ngandelkeun implementasi PHP Disjoint Set di handap ieu pikeun ngahijikeun set sacara efisien. Upami anjeun resep, anjeun tiasa ningali éta dina tindakan di dieu: Kruskal urang Algoritma Maze generator

Kumaha waé, ieu implementasi PHP kuring ngeunaan 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 labirin pikeun senang-senang, struktur data Disjoint Set pastina ogé tiasa dianggo pikeun skenario kahirupan nyata.

Bayangkeun, contona, hiji jaringan sosial anu hoyong nyarankeun babaturan anyar ka pangguna na, teras hayu urang sebutkeun yén urang gaduh genep jalmi anu parantos gaduh hubungan babaturan ieu:

1 jeung 2 teh babaturan.
2 jeung 3 teh babaturan.
4 jeung 5 téh babaturan.
6 teu boga babaturan.

Ngagunakeun algoritma Union-Find kana grup-grup anu misah ieu, urang kedah mendakan hal-hal ieu:

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

Dumasar kana ieu, masuk akal pikeun nyarankeun yén anu ka-1 sareng anu ka-3 kedah janten babaturan, sabab aranjeunna gaduh jalmi ka-2 anu sami.

Tangtosna, dina conto alit sapertos kieu, anjeun tiasa kalayan gampang ningali kanyataan ieu nyalira, tapi efisiensi algoritma ieu ngamungkinkeun éta pikeun diskalakeun sacara layak ka milyaran jalmi sareng grup réréncangan.