Meydan okuma 4
- Algoritmalar kursu
- İleri seviye
- Ders 56/56
- 4 dk
Kruskal ile MST ağırlığını yazdırırsın.
Meydan okuma 4: Kruskal
Bu meydan okumada Kruskal algoritmasını uygulayacaksın. Kenarları sıralayıp döngüsüz ekleyerek minimum çevreli ağacın toplam ağırlığını bulacaksın.
Kenarlar: [(0, 1, 1), (1, 2, 2), (0, 2, 3), (1, 3, 4), (2, 3, 5)]. MST ağırlığı 7'dir.
Uygulama mst_total fonksiyonu
mst_total(edges, n) yaz. find ve union hazır; kenarları sırala, döngüsüz ekle, topla. print(mst_total([(0, 1, 1), (1, 2, 2), (0, 2, 3), (1, 3, 4), (2, 3, 5)], 4)) ile 7 yazdır.
Başlangıç kodu
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_total(edges, n):
# MST toplam ağırlığını bulÖrnek çözüm
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_total(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_total([(0, 1, 1), (1, 2, 2), (0, 2, 3), (1, 3, 4), (2, 3, 5)], 4))Beklenen çıktı
7
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Kruskal'ın ilk adımı nedir?
- Düğümleri ziyaret
- Ağacı büyüt
- Döngü bul
- Kenarları sırala Doğru cevap
Açıklama: İlk adım kenarları ağırlığa göre sıralamaktır.
2 Meydan okuma 4: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
(0,1,1) |
İlk eklene |
(1,2,2) |
İkinci |
(1,3,4) |
Üçüncü |
(0,2,3) |
Atla |
3 toplam hesabı
Soru
total ____ w
Cevap
total += wAçıklama: += doğru.