Özet - Prim

Prim uygulayıp MST ağırlığını yazdıran mini görev yaparsın.

Özet - Prim

Bu grupta tek düğümden başlayarak MST bulan Prim algoritmasını öğrendin. Komşuluk matrisi, min_key ve ziyaret kümesi 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_total fonksiyonu

mst_total(graph) yaz. min_key hazır; her tür en düşük düğümü seç, komşuları güncelle, topla. print(mst_total(init_graph())) ile 19 yazdır.

Örnek çözümü göster

def init_graph():
    # Komşuluk matrisini döndür
    return [[0, 10, 6, 5], [10, 0, 0, 15], [6, 0, 0, 4], [5, 15, 4, 0]]
def min_key(keys, visited):
    # En küçük keys'e sahip ziyaret edilmemiş indeksi bul
    best = float('inf')
    idx = -1
    for i in range(len(keys)):
        if not visited[i] and keys[i] < best:
            best = keys[i]
            idx = i
    return idx
def mst_total(graph):
    # MST toplam ağırlığını bul
    n = len(graph)
    keys = [float('inf')] * n
    keys[0] = 0
    visited = [False] * n
    total = 0
    for _ in range(n):
        u = min_key(keys, visited)
        visited[u] = True
        total += keys[u]
        for v in range(n):
            if graph[u][v] and not visited[v] and graph[u][v] < keys[v]:
                keys[v] = graph[u][v]
    return total
print(mst_total(init_graph()))

Kendini test et

Prim ile Kruskal'ın ortak çıktısı nedir?
- Kenar listesi
- Düğüm sırası
- Döngü sayısı
- MST ağırlığı
Cevabı göster

MST ağırlığı — Her ikisi de MST ağırlığını döndürür.
visited güncelleme
```
visited[____] = True
```
Cevabı göster
```
visited[u] = True
```
Özet - Prim: kavramları eşleştir

init_graph

Matris
min_key

Seçim
prim

MST
keys

Maliyet

Sıradaki ders: Bağımlılık sırası

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler