Union-Find Nedir? Online Connectivity Lab ile Görün

Bir ağdaki iki noktanın birbirine bağlı olup olmadığını sürekli cevaplamak zorunda olduğumuzu düşünelim. Yeni bağlantılar birer birer geliyor; her yeni pair sonrasında hangi noktaların aynı connected component içinde olduğunu bilmek istiyoruz. Bütün ağı her soruda baştan taramak çalışabilir, fakat veri büyüdükçe gereksiz derecede pahalı hale gelir.

Union-Find, diğer adıyla Disjoint Set Union (DSU), bu online connectivity problemini iki temel operasyonla yönetir: bir elemanın ait olduğu component’i bulmak ve iki farklı component’i birleştirmek. Basit görünen bu iki operasyonun nasıl temsil edildiği, toplam çalışma maliyetini tamamen değiştirir.

Websoftik Academy’de geliştirdiğimiz Online Connectivity Lab, Quick Find, Quick Union ve Weighted Quick Union stratejilerini aynı pair stream üzerinde çalıştırır; array güncellemelerini, root yürüyüşlerini, tree bağlantılarını, aktif C kod satırını ve maliyet değişimini adım adım gösterir.

1. Online Connectivity Problemi Nedir?

Elimizde 0 ile n - 1 arasında numaralandırılmış noktalar ve zaman içinde gelen (p, q) bağlantıları olsun. Her pair, p ile q arasında doğrudan bir bağlantı kurulduğunu söyler. İki nokta doğrudan bağlı olmasa bile aralarında bir yol varsa aynı component içindedir.

“Online” kelimesi bütün bağlantıların baştan bilinmesi gerekmediğini anlatır. Pair’ler sırayla gelir ve veri yapısı her yeni bağlantıdan sonra sorulara cevap verebilmelidir:

• p ve q zaten aynı component içinde mi?
• Değillerse iki component nasıl birleştirilmeli?
• İşlemden sonra kaç ayrı component kaldı?
• Seçilen representation find ve union maliyetini nasıl etkiliyor?

2. Union-Find ve Disjoint Set Union Aynı Şey mi?

Evet. Union-Find, Disjoint Set veya DSU adları çoğu kaynakta aynı abstract data type için kullanılır. “Disjoint”, kümelerin birbirini kesmediğini; her elemanın aynı anda yalnızca bir component’e ait olduğunu ifade eder.

• find(p): p elemanının component temsilcisini bulur.
• connected(p, q): iki elemanın temsilcilerini karşılaştırır.
• union(p, q): farklı component’leri tek component haline getirir.

Interface aynı kalırken iç representation değişebilir. Union-Find konusunun asıl öğretici tarafı budur: aynı problemi çözen farklı veri düzenleri, operasyon maliyetleri arasında farklı trade-off’lar oluşturur.

3. Online Connectivity Lab Nasıl Çalışıyor?

Online Connectivity Lab çalışma alanı, üç Union-Find stratejisini yapılandırılmış bir öğrenme yolunda sunar. Aynı input stream bütün stratejilere uygulanabildiği için yalnızca son component sayısını değil, bu sonuca ulaşmak için ödenen maliyeti de karşılaştırabilirsiniz.

Her workspace içinde trace playback, canlı veri yapısı, aktif C kaynak satırı, invariant açıklaması ve cost inspector birlikte ilerler. Quick Find için array scan ve rewrite; Quick Union için root walk; Weighted Quick Union için tree size ve küçük ağacın büyük root’a bağlanması görünür hale gelir.

4. Quick Find Component’leri Nasıl Temsil Eder?

Quick Find yaklaşımında id[i], i elemanının component kimliğini doğrudan saklar. İki eleman aynı id değerine sahipse bağlıdır. Bu invariant sayesinde connectivity kontrolü iki array erişimi ve bir karşılaştırmayla yapılır.

bool connected(int p, int q) {
  return id[p] == id[q];
}

Bu nedenle Quick Find adındaki “quick” ifadesi find operasyonunu anlatır. find maliyeti Θ(1), kullanılan ek bellek ise Θ(n) seviyesindedir.

5. Quick Find Union İşlemi Neden Pahalıdır?

p ile q farklı component’lerdeyse Quick Find, p component’ine ait bütün array hücrelerini bulup q component kimliğiyle yeniden etiketler. Bunun için id[] dizisinin tamamı taranmalıdır.

int p_id = id[p];
int q_id = id[q];

for (int i = 0; i < n; i++)
  if (id[i] == p_id)
      id[i] = q_id;

Tek bir union Θ(n) maliyetindedir. Çok sayıda union içeren bir stream’de bu eager update yaklaşımı pahalılaşır. Lab, taranan ve gerçekten yeniden yazılan hücreleri farklı renklerle göstererek maliyetin nereden geldiğini açıklar.

6. Quick Union Parent Forest Modelini Nasıl Kurar?

Quick Union, component kimliğini her elemana tekrar tekrar yazmak yerine parent pointer’lardan oluşan bir forest kullanır. id[i] artık i düğümünün parent’ını tutar. Root düğümde id[root] == root invariant’ı geçerlidir.

int root(int i) {
  while (i != id[i])
      i = id[i];
  return i;
}

Union için önce iki root bulunur, sonra bir root diğerine bağlanır. Bütün array’i yeniden etiketlemek gerekmez; ancak find artık parent chain boyunca yürümek zorundadır. Parent, root ve forest kavramlarını ayrıntılı çalışmak için Trees & BST Lab rehberimizi kullanabilirsiniz.

7. Quick Union’da Tall Tree Problemi Nasıl Oluşur?

Quick Union hangi root’un diğerinin altına bağlandığını kontrol etmez. Pair sırası sürekli mevcut ağacın root’unu yeni bir root’un altına taşıyorsa uzun bir chain oluşabilir. Böyle bir skewed tree’de root’a ulaşmak için yaklaşık n parent bağlantısı izlenir.

Bu nedenle Quick Union için find ve union operasyonları en kötü durumda O(n) olabilir. Online Connectivity Lab’deki Tall chain hazır senaryosu, kötü pair sırasının görünüşte ucuz link işlemlerini nasıl lineer root yürüyüşlerine dönüştürdüğünü gösterir.

8. Weighted Quick Union Ağacı Nasıl Dengeler?

Weighted Quick Union her root için tree size bilgisini sz[] dizisinde tutar. Union sırasında küçük ağacın root’u büyük ağacın root’una bağlanır. Yalnızca iki size aynıysa yeni ağacın yüksekliği artabilir.

if (sz[p_root] < sz[q_root]) {
  id[p_root] = q_root;
  sz[q_root] += sz[p_root];
} else {
  id[q_root] = p_root;
  sz[p_root] += sz[q_root];
}

Bu union by size kuralı, küçük bir tree’nin büyük bir tree’yi gereksiz yere derinleştirmesini engeller. Lab, her root’un size değerini ve seçilen bağlantı yönünü aynı trace adımında gösterir.

9. Weighted Quick Union Neden Logaritmik Yükseklik Sağlar?

Bir düğümün depth değeri yalnızca bulunduğu tree daha büyük veya eşit büyüklükte başka bir tree’nin altına bağlandığında artar. Bu gerçekleştiğinde yeni tree’nin eleman sayısı en az iki katına çıkar. Bir size değeri en fazla n olabileceği için aynı düğümün depth’i en fazla yaklaşık log₂ n kez artabilir.

Sonuç olarak tree height O(log n) ile sınırlanır; find ve union da O(log n) olur. Bu büyüme farkını sayılar ve grafik üzerinden yeniden incelemek için Complexity Lab rehberimize geçebilirsiniz.

10. Pair Stream ve Micro-Step Trace Neyi Gösterir?

Bir Union-Find algoritmasının yalnızca son id[] dizisine bakmak, hangi array erişimlerinin ve parent yürüyüşlerinin gerçekleştiğini gizler. Online Connectivity Lab her pair’i lookup, root walk, compare, scan, link, rewrite ve component update gibi deterministik micro-step’lere ayırır.

Trace kontrolüyle adımlar tek tek ilerletilebilir; aktif C kod satırı, canlı structure ve cost inspector eş zamanlı güncellenir. Böylece aynı (p, q) pair’inin üç stratejide neden farklı sayıda read, write ve link ürettiği görülebilir.

11. Repeated Pair ve Component Sayısı Nasıl Yönetilir?

p ve q zaten bağlıysa yeni bir union yapılmamalı ve component sayısı azaltılmamalıdır. Fakat “zaten bağlı” sonucuna ulaşmanın kendisi ücretsiz değildir: Quick Find iki doğrudan lookup yaparken tree tabanlı yöntemler iki root walk gerçekleştirebilir.

Lab’deki Repeated checks senaryosu bu ayrımı görünür kılar. Her başarılı component merge işleminde count bir azalır; redundant pair’de structure değişmez. Bu kontrol, Union-Find implementasyonlarında sık görülen yanlış component count hatalarını önler.

12. Üç Union-Find Stratejisinin Karmaşıklıkları Nasıl Karşılaştırılır?

• Quick Find: find Θ(1), union Θ(n), space Θ(n).
• Quick Union: find ve union worst-case O(n), space Θ(n).
• Weighted Quick Union: find ve union O(log n), space Θ(n).

“En iyi algoritma hangisi?” sorusu workload bilinmeden eksiktir. Çok fazla query ve çok az union bulunan sabit bir yapıda Quick Find’in lookup avantajı anlamlı olabilir. Pair sırası bilinmiyor ve tree’nin uzaması istenmiyorsa Weighted Quick Union daha güvenli bir genel seçimdir. Lab’deki decision practice kartları, complexity bilgisini bu tip tasarım kararlarına dönüştürür.

13. Path Compression ve Gerçek Kullanım Alanları Nelerdir?

Weighted Quick Union’dan sonraki yaygın optimizasyon path compression yöntemidir. Bir find sırasında ziyaret edilen düğümler root’a veya root’a daha yakın noktalara bağlanır. Union by size/rank ile path compression birlikte kullanıldığında amortized maliyet pratikte sabite çok yakın hale gelir. Lab’in üç temel stratejisi bu optimizasyona geçmeden önce representation trade-off’unu görünür kılmaya odaklanır.

Union-Find; Kruskal minimum spanning tree, ağ bileşenleri, dinamik grup birleştirme, image segmentation ve eşdeğerlik sınıfları gibi alanlarda kullanılır. Bu problemlerin ortak noktası, elemanlar arasındaki bağlantıların zamanla eklenmesi ve “aynı gruptalar mı?” sorusunun sık sorulmasıdır.

14. Online Connectivity Lab Nasıl Çalışılmalı?

1. Quick Find’de eşit id değerlerinin neden aynı component’i gösterdiğini açıklayın.
2. Her union öncesinde değişecek array hücrelerini tahmin edin.
3. Quick Union’da root path’lerini kağıda çizip trace ile karşılaştırın.
4. Tall chain preset’iyle kötü input sırasının maliyetini gözlemleyin.
5. Weighted Quick Union’da hangi root’un neden child seçildiğini size değerleriyle savunun.
6. Aynı custom pair stream’i üç stratejide çalıştırıp read, write ve link sayılarını karşılaştırın.
7. Knowledge check ve decision practice sorularını görselleştirmeyi kapattıktan sonra yeniden çözün.

Union-Find öğrenmenin hedefi üç kod parçasını ezberlemek değildir. Asıl hedef, representation seçiminin find ve union maliyetini neden değiştirdiğini, input sırasının tree shape’i nasıl etkilediğini ve dengeleme invariant’ının hangi garantiyi sağladığını açıklayabilmektir.

Tüm interaktif araçları Websoftik Academy Lab sayfasında inceleyebilir veya Online Connectivity Lab’i açarak Quick Find’den başlayabilirsiniz. Konuyu daha geniş bir sıraya yerleştirmek için algoritma ve veri yapıları çalışma yol haritamızı kullanabilirsiniz.