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

Yayınlandı: 16 Şubat 2025 12:27:29 UTC
Son güncelleme: 26 Ocak 2026 10:36:59 UTC

Bu makale, minimum spanning tree algoritmalarında Union-Find için yaygın olarak kullanılan Disjoint Set veri yapısının PHP uygulamasını sunmaktadı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 Union-Find olarak da bilinen Ayrı Küme Birliği olarak da kullanılır), ayrık (örtüşmeyen) kümelere eleman bölümlerini yönetmek için kullanılan bir veri yapısıdır. İki önemli işlemi verimli şekilde destekler:

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

Bu yapı, özellikle Kruskal algoritması gibi minimum spanning ağaç algoritmalarında faydalıdır.

Kruskal'ın algoritmasının rastgele labirentler oluşturmak için kullandığı, aşağıdaki PHP uygulamasına dayanan ve kümeleri verimli şekilde birleştiren bir uygulamam var. İlgileniyorsanız, burada iş başında izleyebilirsiniz: Kruskal Algoritması Labirent Oluşturucu

Her neyse, bu benim Disjoint Set'in PHP uygulaması:

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

Labirentleri eğlence için yaratmanın yanı sıra, Disjoint Set veri yapısı gerçek hayat senaryoları için de kullanılabilir.

Örneğin, kullanıcılarına yeni arkadaşlar önermek isteyen bir sosyal ağı hayal edin ve diyelim ki bu arkadaş ilişkilerine sahip altı kişi var:

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

Union-Find algoritmasını bu ayrı gruplara uygularsak, aşağıdakileri bulmalıyız:

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

Buna dayanarak, 1 ve 3'ün arkadaş olması gerektiğini önermek mantıklı olur, çünkü 2. kişiyle ortak noktaları var.

Tabii ki, böyle küçük bir örnekte bu gerçeği kendiniz kolayca fark edebilirsiniz, ancak bu algoritmanın verimliliği sayesinde milyarlarca insan ve arkadaş grubuna ölçeklenebilir.