PHP'de Ayrık Küme (Birleşim Bulma Algoritması)

Yayınlandı: 16 Şubat 2025 12:27:29 UTC

Bu makalede, minimum yayılan ağaç algoritmalarında Birlik Bulma için yaygın olarak kullanılan Ayrık Küme veri yapısının PHP uygulaması ele alınmaktadır.

Bu sayfa, mümkün olduğunca çok kişi tarafından erişilebilir olması amacıyla İngilizce'den makine çevirisiyle çevrilmiştir. Ne yazık ki, makine çevirisi henüz mükemmelleştirilmiş bir teknoloji değildir, bu nedenle hatalar meydana gelebilir. Tercih ederseniz, orijinal İngilizce versiyonu buradan görüntüleyebilirsiniz:

Disjoint Set (Union-Find Algorithm) in PHP

Ayrık Küme (genellikle Birleştirme-Bul için kullanılır, diğer adıyla Ayrık Küme Birliği), öğelerin ayrık (örtüşmeyen) kümelere bölünmesini yönetmek için kullanılan bir veri yapısıdır. İki temel işlemi verimli bir şekilde destekler:

Bul : Bir elemanın hangi kümeye ait olduğunu belirler.
Birleşim : İki kümeyi birleştirir.

Bu yapı özellikle Kruskal algoritması gibi minimum yayılan ağaç algoritmalarında kullanışlıdır.

Aşağıdaki Disjoint Set PHP uygulamasına dayanan ve kümeleri verimli bir şekilde birleştirmek için kullanılan rastgele labirentler üretmek için kullanılan Kruskal algoritmasının bir uygulamasına sahibim. Eğer ilgileniyorsanız, bunu burada eylem halinde görebilirsiniz: Kruskal Algoritması Labirent Oluşturucu

Neyse, Disjoint Set'in PHP versiyonu şu şekilde:

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]++;
            }
        }
    }
}

Eğlence amaçlı labirentler oluşturmanın yanı sıra, Disjoint Set veri yapısı gerçek yaşam senaryoları için de kullanılabilir.

Örneğin, kullanıcılarına yeni arkadaşlar önermek isteyen bir sosyal ağ olduğunu ve bu arkadaşlık ilişkilerine sahip altı kişinin olduğunu varsayalım:

1 ve 2 arkadaştır.
2 ve 3 arkadaştır.
4 ve 5 arkadaştır.
6'nın hiç arkadaşı yok.

Bu ayrı gruplara Birlik-Bul algoritmasını uyguladığımızda aşağıdakileri bulmalıyız:

1, 2 ve 3 bir grupta.
4 ve 5 ikinci grupta.
Üçüncü grupta 6 kişi var.

Buradan yola çıkarak 1 ve 3'ün arkadaş olmaları gerektiğini öne sürmek mantıklı olacaktır, çünkü 2 numaralı kişiyle ortak noktaları var.

Elbette, bunun gibi küçük bir örnekte, siz de bu gerçeği kolaylıkla fark edebilirsiniz, ancak bu algoritmanın verimliliği, milyarlarca insana ve arkadaş grubuna uygulanabilir şekilde ölçeklenmesine olanak tanır.