Özet - Kruskal
- Algoritmalar kursu
- İleri seviye
- Ders 40/56
- 4 dk
Kruskal uygulayıp MST ağırlığını yazdıran mini görev yaparsın.
Özet - Kruskal
Bu grupta kenarları sıralayıp döngüsüz ekleyerek MST bulan Kruskal algoritmasını öğrendin. Kenar listesi, sıralama ve döngü denetimi birleşince çözüm oluşur.
Şimdi tüm parçaları bir araya getiren bir fonksiyon yazacaksın. Bu özet, grubun kavramlarını tek bir kodda birleştirir.
Uygulama mst_weight fonksiyonu
mst_weight(edges, n) yaz. find ve union hazır; kenarları sırala, döngüsüz ekle, toplamı döndür. print(mst_weight(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 mst_weight(edges, n):
# MST toplam 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 mst_weight(edges, n):
# MST toplam 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(mst_weight(init_edges(), 4))Beklenen çıktı
19
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Kruskal'ın çıktısı nedir?
- Kenar listesi
- Düğüm listesi
- Döngü sayısı
- Toplam ağırlık Doğru cevap
Açıklama: Kruskal MST'nin toplam ağırlığını döndürür.
2 toplam değişkeni
Soru
total ____ w
Cevap
total += wAçıklama: += doğru.
3 Özet - Kruskal: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
init_edges |
Kenar |
sort_edges |
Sırala |
find |
Kök |
kruskal |
MST |