Özet - Kruskal

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.

Örnek çözümü göster

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))

Kendini test et

Kruskal'ın çıktısı nedir?
- Kenar listesi
- Düğüm listesi
- Döngü sayısı
- Toplam ağırlık
Cevabı göster

Toplam ağırlık — Kruskal MST'nin toplam ağırlığını döndürür.
toplam değişkeni
```
total ____ w
```
Cevabı göster
```
total += w
```
Özet - Kruskal: kavramları eşleştir

init_edges

Kenar
sort_edges

Sırala
find

Kök
kruskal

MST

Sıradaki ders: Prim mantığı

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler