Ayrık Kümeler

Bir ağdaki iki bilgisayarın birbirine — doğrudan ya da aracılarla — bağlı olup olmadığı sorulsun. Bağlantılar zamanla ekleniyor, hiç kaldırılmıyor. İki soru dönüşümlü olarak geliyor: “şu ikisi aynı grupta mı?” ve “şu iki grubu birleştir.”

Bu, ayrık kümeler (disjoint sets) yapısının — diğer adıyla birleştir–bul (union–find) — çözdüğü problemdir. Adı, kümelerin kesişimsiz olmasından gelir: her eleman tam olarak bir gruba aittir.

İki İşlem

İşlem	Anlamı
bul(x)	x’in ait olduğu grubun temsilcisini döndürür
birlestir(x, y)	İki elemanın gruplarını tek grupta toplar

“Aynı grupta mı” sorusu ayrı bir işlem gerektirmez: iki elemanın temsilcileri aynıysa aynı gruptadırlar.

Temsilci, grubun herhangi bir elemanıdır; hangi eleman olduğu önemsizdir, önemli olan aynı gruptaki tüm elemanların aynı temsilciyi bulmasıdır.

Orman Gösterimi

Yapı, her grubu bir ağaç olarak tutar; ağacın kökü grubun temsilcisidir. Tüm gruplar bir arada bir orman oluşturur.

Gösterim tek bir dizidir: ust[x], x’in bir üst düğümünü tutar. Kök, kendini gösterir.

ust:  [0, 0, 1, 3, 3]
       ↑
       0 ve 3 kök (kendini gösteriyor)

grup 1: 0 ← 1 ← 2        grup 2: 3 ← 4

bul işlemi, kök bulunana kadar üst bağları izler. birlestir, iki kökten birini diğerine bağlar.

Bu saf hâliyle yapı, kötü durumda dejenere olabilir: her birleştirme kökü uzun bir zincirin ucuna eklerse ağaç bir bağlı listeye döner ve bul işlemi $O(n)$ olur.

İki İyileştirme

Sıraya göre birleştirme. Birleştirmede, küçük ağacın kökü büyüğüne bağlanır. Böylece derinlik ancak eşit büyüklükteki iki ağaç birleştiğinde artar; ağaç yüksekliği $O(\log n)$ ile sınırlanır. Büyüklük ölçütü olarak eleman sayısı veya tahmini yükseklik (sıra) kullanılır. İkisi de aynı sınırı verir; eleman sayısı, grup büyüklüğünün ayrıca sorulabilmesi gibi bir yan yarar sağladığı için sık tercih edilir. Yol sıkıştırma uygulandığında tahmini yükseklik gerçek yüksekliği aşabilir — bu, ölçütün yalnızca birleştirme kararında kullanıldığı ve kesinliğinin gerekmediği anlamına gelir.

Yol sıkıştırma. bul işlemi kökü bulurken, yol üzerindeki tüm düğümleri doğrudan köke bağlar. Bir sonraki sorgu aynı yolu tekrar izlemez. İşlem, sorgunun yan ürünü olarak yapıyı düzleştirir.

İkisi birlikte uygulandığında, $m$ işlemin toplam maliyeti neredeyse doğrusaldır: işlem başına düşen amortize maliyet, pratikte sabit kabul edilebilecek kadar yavaş büyüyen bir fonksiyonla sınırlıdır. Kesin ifade ve kanıtı İleri Algoritmalar kursuna aittir; bu kurs için yeterli olan, iki iyileştirmenin birlikte kullanıldığıdır.

class AyrikKumeler:
    """Birleştir–bul; sıraya göre birleştirme ve yol sıkıştırma ile."""

    def __init__(self, n: int) -> None:
        self._ust = list(range(n))       # başlangıçta herkes kendi grubunda
        self._boyut = [1] * n
        self.grup_sayisi = n

    def bul(self, x: int) -> int:
        kok = x
        while self._ust[kok] != kok:     # köke kadar çık
            kok = self._ust[kok]
        while self._ust[x] != kok:       # yol sıkıştırma: yolu köke bağla
            self._ust[x], x = kok, self._ust[x]
        return kok

    def birlestir(self, x: int, y: int) -> bool:
        a, b = self.bul(x), self.bul(y)
        if a == b:
            return False                 # zaten aynı grupta
        if self._boyut[a] < self._boyut[b]:
            a, b = b, a                  # büyük ağaç kök olsun
        self._ust[b] = a
        self._boyut[a] += self._boyut[b]
        self.grup_sayisi -= 1
        return True

    def ayni_grupta_mi(self, x: int, y: int) -> bool:
        return self.bul(x) == self.bul(y)


ak = AyrikKumeler(6)                     # 0..5 arası altı eleman
ak.birlestir(0, 1)
ak.birlestir(1, 2)
ak.birlestir(3, 4)

print(ak.ayni_grupta_mi(0, 2))           # True
print(ak.ayni_grupta_mi(0, 3))           # False
print(ak.grup_sayisi)                    # 3   — {0,1,2}, {3,4}, {5}

print(ak.birlestir(0, 2))                # False — zaten birlikteydiler
ak.birlestir(2, 4)
print(ak.ayni_grupta_mi(1, 3), ak.grup_sayisi)   # True 2

birlestir işleminin mantıksal değer döndürmesi pratik bir ayrıntıdır: çağıran, gerçekten bir birleşme olup olmadığını öğrenir. Bu bilgi, sonraki bölümdeki kullanım alanlarında doğrudan işe yarar.

İzleme

Yapının nasıl düzleştiğini görmek için üst dizisi adım adım incelenebilir:

ak = AyrikKumeler(5)
ak.birlestir(1, 2)
ak.birlestir(3, 4)
ak.birlestir(2, 4)
print(ak._ust)               # [0, 1, 1, 1, 3]  — 3'ün kökü hâlâ dolaylı

ak.bul(4)                    # yol sıkıştırma çalışır
print(ak._ust)               # [0, 1, 1, 1, 1]  — 4 doğrudan köke bağlandı

İlk çıktıda 4 düğümünün kökü iki adımda bulunuyordu (4 → 3 → 1); tek bir bul çağrısından sonra bağ doğrudan köke işaret ediyor. Sıkıştırma ayrı bir bakım işlemi değildir — sorgunun kendisi yapıyı iyileştirir.

Neyi Yapamaz

Yapının bilinen sınırı, ayırmanın desteklenmemesidir. Gruplar birleşir, ayrılmaz. Bir bağlantı kaldırıldığında grupların yeniden hesaplanması gerekir; bu, yapıyı sıfırdan kurmak demektir.

İkinci sınır, grup üyelerinin listelenememesidir. Yapı yalnızca “aynı grupta mı” sorusunu yanıtlar; bir grubun elemanlarını saymak veya listelemek için ek kayıt tutulur.

Bu kısıtlar tesadüf değildir: yapının hızı, tam olarak bu bilgileri tutmamasından gelir.

Kullanım Alanları

Bağlı bileşenler. Bir çizgede hangi düğümlerin birbirine ulaşabildiği, kenarlar eklendikçe bu yapıyla izlenir. Bu kursun son konusunda aynı soru gezinme algoritmalarıyla da yanıtlanacak; ayrık kümeler, kenarların akış hâlinde geldiği durumda daha uygundur.

Minimum kapsayan ağaç. Kenarları ağırlığa göre sıralayıp döngü oluşturmayanları seçen algoritma, “bu kenar döngü oluşturur mu” sorusunu ayrık kümelerle sorar: iki uç zaten aynı gruptaysa kenar atlanır. Algoritmanın kendisi Algoritmalar kursunda ele alınır.

Denklik sınıfları. “Şu ikisi aynı sayılır” biçimindeki kuralların birikimiyle oluşan gruplar — aynı kişiye ait hesapların birleştirilmesi, aynı nesneyi gösteren kayıtların eşleştirilmesi — doğrudan bu yapıyla tutulur.

Izgara problemleri. Bir ızgarada bitişik hücrelerin birleştirilmesiyle oluşan bölgeler (görüntüdeki bağlı alanlar, sızma modelleri) aynı biçimde izlenir.

Yapının bir başka özelliği, işlemlerin sırasından bağımsız sonuç vermesidir: aynı birleştirme kümesi hangi sırayla uygulanırsa uygulansın, oluşan gruplar aynıdır. Değişen yalnızca ağaçların iç biçimidir; bu da sorguların sonucunu etkilemez.

Maliyet Tablosu

Gerçekleştirim	bul	birlestir
Saf orman	$O(n)$	$O(n)$
Sıraya göre birleştirme	$O(\log n)$	$O(\log n)$
+ yol sıkıştırma	Amortize neredeyse sabit	Amortize neredeyse sabit

Özet

• Ayrık kümeler yapısı, elemanları kesişimsiz gruplara ayırır ve iki işlem sunar: grubun temsilcisini bulmak ve iki grubu birleştirmek.
• Gruplar bir orman olarak tutulur; kök, grubun temsilcisidir.
• Sıraya göre birleştirme, küçük ağacı büyüğe bağlayarak yüksekliği logaritmik tutar.
• Yol sıkıştırma, bul sırasında yol üzerindeki düğümleri doğrudan köke bağlayarak yapıyı düzleştirir.
• İkisi birlikte, işlem başına amortize neredeyse sabit maliyet verir.
• Yapı ayırmayı ve grup elemanlarını listelemeyi desteklemez; hızı bu bilgileri tutmamasından gelir.

Sonraki Adım

Bu konuda gruplar için ağaç gösterimi kullanıldı ama ağaçların kendisi tanımlanmadı. Sonraki konu, ağaçları başlı başına ele alacak: terminoloji, gezinme yöntemleri, arama ağaçları, denge sorunu ve öncelik kuyruğunu gerçekleyen yığın yapısı.