Ziyaret kümesi

Ağaca eklenen düğümleri işaretlemeyi öğrenirsin.

Ziyaret kümesi

Seçilen düğüm ziyaret edilmiş olarak işaretlenir ve komşularının keys değerleri güncellenir. Daha kısa bir kenar varsa keys[v] azalır.

Bu işlem n kez tekrar edilir; her turda bir düğüm ağaca katılır. Tüm düğümler ziyaret edilince MST tamamlanır.

Toplam hesabı

Her turda seçilen düğümün keys değeri toplama eklenir. Bu, ağaca katılan kenarın ağırlığıdır. Toplam, MST'nin ağırlığıdır.

Prim'in çıktısı Kruskal'ınkiyle aynıdır: tek bir sayı. Farklı ilerleyiş aynı sonucu verir.

Uygulama prim fonksiyonu

prim(graph) yaz. min_key hazır; her tür en düşük düğümü seç, komşuları güncelle, topla. print(prim(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 prim(graph):
    # MST 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(prim(init_graph()))

Kendini test et

Ziyaret kümesi: kavramları eşleştir

keys[0]

0
keys[1]

10
keys[2]

6
keys[3]

5
Örnek grafta Prim'in MST ağırlığı nedir?
- 25
- 15
- 19
- 10
Cevabı göster

19 — 0+5+4+10=19 (aynı MST).
toplama
```
total += keys[____]
```
Cevabı göster
```
total += keys[u]
```

Sıradaki ders: Özet - Prim

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler