Dinamik Bağlantı Problemi (Dynamic Connectivity)
Bir dizi nesne verildiğinde, iki nesnenin bağlı olup olmadığını verimli bir şekilde sorgulamamız ve yeni bağlantılar eklememiz gerekiyor.
Bu basit görünen problem, bilgisayar biliminin en temel ve en zarif veri yapılarından birini ortaya çıkarmıştır: Union-Find (Disjoint Set Union).
Girdi: N adet nesne (0'dan N-1'e kadar numaralandırılmış)
İşlemler:
İki nesne bağlıdır eğer aralarında bir bağlantı zinciri varsa.
Örnek: A-B ve B-C bağlı ise, A ve C de (dolaylı olarak) bağlıdır.
10 bilgisayardan oluşan bir ağ düşünelim:
"Bağlı olma" ilişkisi matematiksel olarak bir eşdeğerlik ilişkisidir:
| 1. Dönüşlülük (Reflexive) | p, p'ye bağlıdır |
| 2. Simetriklik (Symmetric) | p, q'ya bağlı ise → q, p'ye bağlıdır |
| 3. Geçişlilik (Transitive) | p-q bağlı ve q-r bağlı ise → p-r bağlıdır |
Bu özellikler sayesinde nesneler ayrık kümelere (disjoint sets) ayrılır.
Her kümedeki tüm elemanlar birbirine bağlıdır, farklı kümelerdeki elemanlar ise bağlı değildir.
Veri yapımızın sağlaması gereken temel arayüz:
| Metod | Açıklama |
|---|---|
UnionFind(n) |
N nesne ile boş bir Union-Find yapısı oluştur (başlangıçta N ayrı küme) |
union(p, q) |
p ve q'nun bulunduğu kümeleri birleştir |
find(p) |
p'nin ait olduğu kümenin temsilcisini (identifier) döndür |
connected(p, q) |
p ve q aynı kümede mi? (find(p) == find(q)) |
count() |
Toplam kaç ayrı küme var? |
class UnionFind:
"""
Union-Find (Disjoint Set Union) veri yapısı.
Dinamik bağlantı problemini çözmek için kullanılır.
"""
def __init__(self, n: int):
"""
N nesne ile yeni bir Union-Find yapısı oluşturur.
Başlangıçta her nesne kendi kümesindedir (N ayrı küme).
Args:
n: Nesne sayısı (0'dan n-1'e kadar numaralandırılmış)
"""
pass
def union(self, p: int, q: int) -> None:
"""
p ve q'nun bulunduğu kümeleri birleştirir.
Args:
p: Birinci nesne
q: İkinci nesne
"""
pass
def find(self, p: int) -> int:
"""
p'nin ait olduğu kümenin temsilcisini döndürür.
Aynı kümedeki tüm elemanlar için aynı değeri döndürür.
Args:
p: Sorgulanacak nesne
Returns:
Kümenin temsilci ID'si
"""
pass
def connected(self, p: int, q: int) -> bool:
"""
p ve q'nun aynı kümede olup olmadığını kontrol eder.
Args:
p: Birinci nesne
q: İkinci nesne
Returns:
True eğer aynı kümedeler, False aksi halde
"""
return self.find(p) == self.find(q)
def count(self) -> int:
"""
Mevcut ayrık küme sayısını döndürür.
Returns:
Küme sayısı
"""
passİki bilgisayar birbirine bağlı mı? Hangi bilgisayarlar aynı ağda?
Union: Kablo çek
Connected: Paket gönderilebilir mi?
İki kişi arkadaş zinciri ile bağlı mı? Kaç farklı topluluk var?
Union: Arkadaşlık kur
Connected: Aynı grupta mı?
Benzer pikselleri grupla. Görüntüdeki farklı nesneleri ayır.
Union: Benzer pikselleri birleştir
Connected: Aynı nesne mi?
Minimum Spanning Tree algoritmasında döngü kontrolü.
Union: Kenar ekle
Connected: Döngü oluşur mu?
Su veya elektrik yukarıdan aşağıya akabilir mi?
Union: Hücre aç
Connected: Yol var mı?
Protein etkileşim ağları, gen aileleri.
Union: Etkileşim tespit et
Connected: İlişkili mi?
Bu bölümde, basit ama yavaş çözümlerden başlayarak, çok hızlı bir algoritmaya nasıl ulaşıldığını göreceğiz:
Find işlemi hızlı (O(1)), ama Union yavaş (O(N))
Problem: Her union N eleman günceller
Union işlemi basit, ama ağaç çok uzun olabilir
Problem: Find en kötü O(N)
Küçük ağacı büyüğe bağla → Ağaç yüksekliği O(log N)
İyileşme: Her işlem O(log N)
Find sırasında ağacı düzleştir → Neredeyse sabit süre
Sonuç: Amortize O(α(N)) ≈ O(1)
Basit bir problemle başladık, ama doğru iyileştirmelerle neredeyse doğrusal bir algoritma elde ettik!
N nesne üzerinde M işlem: Naif O(MN) → Optimize O(M × α(N))
Bu bölümün sonunda şunları yapabileceksiniz:
Hazırsanız, Quick-Find algoritmasıyla başlayalım! 🚀