Algoritma Disjoint Set (Union-Find) dalam PHP

Diterbitkan: 16 Februari 2025 pukul 12.25.37 UTC

Artikel ini menyajikan implementasi PHP dari struktur data Disjoint Set, yang umum 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

Disjoint Set (umumnya digunakan untuk Union-Find alias Disjoint Set Union) adalah struktur data yang digunakan untuk mengelola partisi elemen menjadi set yang terpisah (tidak tumpang tindih). Struktur ini mendukung dua operasi utama secara efisien:

Temukan : Menentukan himpunan tempat suatu elemen berada.
Union : Menggabungkan dua set menjadi satu.

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

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

Bagaimana pun, ini adalah implementasi PHP saya untuk 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, sebuah jejaring sosial yang ingin menyarankan teman-teman baru kepada para penggunanya, lalu anggaplah kita sudah memiliki enam orang yang memiliki hubungan pertemanan berikut ini:

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

Dengan menerapkan algoritma Union-Find pada kelompok-kelompok terpisah ini, kita akan menemukan hal berikut:

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

Berdasarkan hal ini, masuk akal untuk menyarankan bahwa 1 dan 3 seharusnya menjadi teman, karena mereka memiliki orang yang sama, yaitu 2.

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