Algoritma Disjoint Set (Union-Find) dalam PHP

Diterbitkan: 16 Februari 2025 pukul 12.25.37 UTC
Terakhir diperbarui: 26 Januari 2026 pukul 10.36.49 UTC

Artikel ini menampilkan implementasi PHP dari struktur data Disjoint Set, yang biasa digunakan untuk Union-Find dalam algoritma pohon rentang minimum.

Halaman ini diterjemahkan oleh mesin dari bahasa Inggris agar dapat diakses oleh sebanyak mungkin orang. Sayangnya, terjemahan mesin belum merupakan teknologi yang sempurna, sehingga kesalahan dapat terjadi. Jika Anda mau, Anda dapat melihat versi bahasa Inggris aslinya di sini:

Disjoint Set (Union-Find Algorithm) in PHP

Set Disjoint (biasanya digunakan untuk Union-Find alias Disjoint Set Union) adalah struktur data yang digunakan untuk mengelola partisi elemen ke dalam himpunan yang terputus-putus (tidak tumpang tindih). Ini mendukung dua operasi utama secara efisien:

Temukan: Menentukan kumpulan mana yang dimiliki elemen.
Union: Menggabungkan dua set bersama-sama.

Struktur ini sangat berguna dalam algoritma pohon rentang minimum, seperti algoritma Kruskal.

Saya memiliki implementasi algoritma Kruskal yang digunakan untuk menghasilkan labirin acak yang mengandalkan implementasi PHP di bawah ini dari Disjoint Set untuk menggabungkan set secara efisien. Jika Anda tertarik, Anda dapat melihatnya beraksi di sini: Generator Labirin Algoritma Kruskal

Bagaimanapun, ini adalah implementasi PHP saya dari 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]++;
            }
        }
    }
}

Selain menghasilkan labirin untuk bersenang-senang, struktur data Disjoint Set tentu juga dapat digunakan untuk skenario kehidupan nyata.

Bayangkan, misalnya, jejaring sosial yang ingin menyarankan teman baru kepada penggunanya, dan kemudian katakanlah kita memiliki enam orang dengan hubungan pertemanan ini yang sudah ada:

1 dan 2 adalah teman.
2 dan 3 adalah teman.
4 dan 5 adalah teman.
6 tidak memiliki teman.

Menerapkan algoritma Union-Find ke grup terpisah ini, kita akan menemukan yang berikut ini:

1, 2 dan 3 dalam satu kelompok.
4 dan 5 dalam kelompok kedua.
6 dalam kelompok ketiga.

Berdasarkan hal ini, masuk akal untuk menyarankan bahwa 1 dan 3 harus menjadi teman, karena mereka memiliki kesamaan orang 2.

Tentu saja, dalam contoh kecil seperti ini, Anda dapat dengan mudah menemukan fakta ini sendiri, tetapi efisiensi algoritme ini memungkinkannya untuk menskalakan ke miliaran orang dan kelompok teman.