Union-find
- Algoritmalar kursu
- İleri seviye
- Ders 49/56
- 4 dk
Ayrık kümeleri birleştiren union-find veri yapısını öğrenirsin.
Union-find
Union-find, bir grafiğin düğümlerini kümeler halinde izler. find(x) x'in kökünü bulur; union(x, y) iki küreyi birleştirir.
Bu yapı, Kruskal'ın döngü denetiminde kullanılır. Her düğüm bir ata (parent) gösterir; kök olan düğüm kendine işaret eder.
Ata dizisi
Her düğümün bir atası (parent) vardır. Başlangıçta her düğüm kendi atasıdır: parent[i] = i. Birleşme olunca ata güncellenir.
Kök bulma, ata zincirini takip eder: while parent[x] != x: x = parent[x]. Bu döngü kökü bulana kadar devam eder.
Uygulama init_parent fonksiyonu
init_parent(n) yaz. Her düğümün kendisi olduğu ata dizisini döndür. print(init_parent(4)) ile yazdır.
Başlangıç kodu
def init_parent(n):
# Ata dizisini döndürÖrnek çözüm
def init_parent(n):
# Ata dizisini döndür
return list(range(n))
print(init_parent(4))Beklenen çıktı
[0, 1, 2, 3]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 find(x) ne döndürür?
- x'in kökünü Doğru cevap
- Kendi kökünü
- Komşularını
- Ağırlığını
Açıklama: find(x) x'in kökünü döndürür.
2 başlangıç atası
parent[i] = ____parent[i] = iAçıklama: i doğru.
3 Union-find: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
find |
Kök bul |
union |
Kümeleri birleştir |
parent |
Ata dizisi |
root |
Kendi kendine |