Set Disjoint (Algoritma Pencarian Kesatuan) dalam PHP

Diterbitkan: 19 Mac 2025 pada 9:36:29 PTG UTC

Artikel ini menampilkan pelaksanaan PHP bagi struktur data Set Disjoint, yang biasa digunakan untuk Union-Find dalam algoritma pepohon rentang minimum.

Halaman ini telah diterjemahkan mesin daripada bahasa Inggeris untuk menjadikannya boleh diakses oleh seramai mungkin orang. Malangnya, terjemahan mesin belum lagi merupakan teknologi yang sempurna, jadi ralat boleh berlaku. Jika anda mahu, anda boleh melihat versi bahasa Inggeris asal di sini:

Disjoint Set (Union-Find Algorithm) in PHP

Set Tak Bersilang (biasanya digunakan untuk Union-Find atau Set Tak Bersilang Union) adalah struktur data yang digunakan untuk menguruskan pemisahan elemen ke dalam set yang tak bersilang (tidak bertindih). Ia menyokong dua operasi utama dengan cekap:

Find: Menentukan set mana satu elemen tergolong.
Union: Menggabungkan dua set bersama.

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

Saya mempunyai pelaksanaan algoritma Kruskal yang digunakan untuk menjana labirin rawak yang bergantung pada pelaksanaan PHP Set Tak Bersilang di bawah untuk menggabungkan set dengan cekap. Jika anda berminat, anda boleh melihatnya dalam tindakan di sini: Penjana Maze Algoritma Kruskal

Bagaimanapun, ini adalah pelaksanaan PHP saya untuk Set Tak Bersilang:

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 menjana labirin untuk berseronok, struktur data Set Tak Bersilang juga boleh digunakan untuk situasi kehidupan sebenar.

Bayangkan, sebagai contoh, sebuah rangkaian sosial yang ingin mencadangkan kawan baru kepada penggunanya, dan katakanlah kita mempunyai enam orang dengan hubungan kawan seperti berikut:

1 dan 2 adalah kawan.
2 dan 3 adalah kawan.
4 dan 5 adalah kawan.
6 tiada kawan.

Menggunakan algoritma Union-Find pada kumpulan-kumpulan terpisah ini, kita sepatutnya mendapati yang berikut:

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

Berdasarkan ini, adalah masuk akal untuk mencadangkan bahawa 1 dan 3 harus menjadi kawan, kerana mereka mempunyai orang 2 yang sama.

Sudah tentu, dalam contoh kecil seperti ini, anda boleh dengan mudah melihat fakta ini sendiri, tetapi kecekapan algoritma ini membolehkannya berkembang ke berbilion orang dan kumpulan kawan dengan praktikal.