--- title: 'Ayrık Kümeler' source: 'https://academia.sh/tr/kurslar/veri-yapilari/ayrik-kumeler' course: 'Veri Yapıları' language: tr updated: '2026-08-17T18:07:50+00:00' license: 'CC BY-SA 4.0' --- # Ayrık Kümeler Dinamik gruplama problemi, birleştir–bul yapısı, sıraya göre birleştirme, yol sıkıştırma ve kullanım alanları. 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. ```python 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: ```python 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ı.