Döngü kontrolü
- Algoritmalar kursu
- İleri seviye
- Ders 39/56
- 4 dk
Eklenen kenar döngü oluşturursa atlamayı öğrenirsin.
Döngü kontrolü
Bir kenar ekleneceği zaman uçları aynı kümede mi diye denetlenir. Aynı kümedeyse kenar döngü oluşturur ve atlanır.
Bu denetim, union-find veri yapısıyla yapılır. Her düğüm bir küme olarak başlar; kenar eklendikçe kümeler birleşir.
Toplam ağırlık
Her eklenen kenarın ağırlığı toplama eklenir. n-1 kenar eklenince MST tamamlanır ve toplam ağırlık döndürülür.
Kruskal'ın çıktısı tek bir sayıdır: MST'nin toplam ağırlığı. Bu, ağacı oluşturmanın en düşük maliyetidir.
Uygulama kruskal fonksiyonu
kruskal(edges, n) yaz. find ve union hazır; kenarları sırala, döngü oluşturmayanları ekle, toplamı döndür. print(kruskal(init_edges(), 4)) ile 19 yazdır.
Başlangıç kodu
def init_edges():
# Kenar listesini döndür
return [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
def find(parent, x):
while parent[x] != x:
x = parent[x]
return x
def union(parent, x, y):
px, py = find(parent, x), find(parent, y)
if px != py:
parent[px] = py
def kruskal(edges, n):
# MST ağırlığını bulÖrnek çözüm
def init_edges():
# Kenar listesini döndür
return [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
def find(parent, x):
while parent[x] != x:
x = parent[x]
return x
def union(parent, x, y):
px, py = find(parent, x), find(parent, y)
if px != py:
parent[px] = py
def kruskal(edges, n):
# MST ağırlığını bul
edges = sorted(edges, key=lambda e: e[2])
parent = list(range(n))
total = 0
for u, v, w in edges:
if find(parent, u) != find(parent, v):
union(parent, u, v)
total += w
return total
print(kruskal(init_edges(), 4))Beklenen çıktı
19
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Döngü kontrolü: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
find |
Kök bul |
union |
Kümeleri birleştir |
parent |
Ata dizisi |
döngü |
Atla |
2 Örnek grafta MST'nin toplam ağırlığı nedir?
- 15
- 20
- 19 Doğru cevap
- 25
Açıklama: 4+5+10=19.
3 döngü koşulu
if find(parent, u) ____ find(parent, v):if find(parent, u) != find(parent, v):Açıklama: != doğru.