Disjoint Set (Union-Find Algorithm) ing PHP

Diterbitake: 16 Februari 2025 ing 12:29:55 UTC
Dianyari pungkasan: 26 Januari 2026 ing 10:37:08 UTC

Artikel iki nampilake implementasi PHP saka struktur data Disjoint Set, sing umum digunakake kanggo Union-Find ing algoritma wit rentang minimum.

Kaca iki diterjemahake mesin saka basa Inggris supaya bisa diakses dening akeh wong. Sayange, terjemahan mesin durung dadi teknologi sing sampurna, mula kesalahan bisa kedadeyan. Yen sampeyan seneng, sampeyan bisa ndeleng versi Inggris asli ing kene:

Disjoint Set (Union-Find Algorithm) in PHP

Set Disjoint (sing umum digunakake kanggo Union-Find alias Disjoint Set Union) yaiku struktur data sing digunakake kanggo ngatur partisi elemen dadi set sing ora saling tumpang tindih (ora tumpang tindih). Iki ndhukung rong operasi kunci kanthi efisien:

Golek (Find) : Nemtokake himpunan endi sing kalebu elemen kasebut.
Gabungan : Nggabungake rong himpunan dadi siji.

Struktur iki migunani banget ing algoritma wit rentang minimum, kayata algoritma Kruskal.

Aku duwe implementasi algoritma Kruskal sing digunakake kanggo nggawe labirin acak sing gumantung marang implementasi PHP ing ngisor iki saka Disjoint Set kanggo nggabungake set kanthi efisien. Yen sampeyan kasengsem, sampeyan bisa ndeleng ing kene: Generator labirin Algoritma Kruskal

Oiya, iki implementasi PHP-ku saka 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]++;
            }
        }
    }
}

Saliyané nggawé labirin kanggo seneng-seneng, struktur data Disjoint Set mesthi uga bisa digunakaké kanggo skenario nyata.

Umpamane, bayangna jaringan sosial sing pengin menehi saran kanca anyar marang para panganggone, banjur ayo padha anggep ana enem wong sing wis duwe hubungan kanca kaya iki:

1 lan 2 iku kanca.
2 lan 3 iku kanca.
Nomer 4 lan 5 iku kanca.
6 ora duwe kanca.

Nglamar algoritma Union-Find kanggo klompok-klompok sing kapisah iki, kita kudu nemokake ing ngisor iki:

1, 2 lan 3 ing sak klompok.
4 lan 5 ing klompok kapindho.
6 ing klompok katelu.

Adhedhasar iki, masuk akal yen menehi saran supaya wong 1 lan 3 dadi kanca, amarga dheweke duwe wong 2 sing padha.

Mesthi wae, ing conto cilik kaya iki, sampeyan bisa kanthi gampang nemokake kasunyatan iki dhewe, nanging efisiensi algoritma iki ngidini bisa diskalakake kanthi layak menyang milyaran wong lan klompok kanca.