Prim mantığı

Bir düğümden başlayıp her adımda en ucuz kenarı ekleyen algoritmayı öğrenirsin.

Prim algoritması, MST'yi tek bir düğümden başlayarak büyüterek bulur. Her adımda ağaca en düşük ağırlıklı kenarla bağlanan yeni bir düğüm eklenir.

Kruskal kenarları sıralarken, Prim ağacı genişletir. İkisi de aynı MST ağırlığını verir ama farklı ilerler.

Komşuluk matrisi

Prim, komşuluk matrisiyle çalışır. graph[i][j], i ve j arasındaki kenar ağırlığıdır; kenar yoksa 0'dır. Matris simetriktir.

Her düğümün tüm komşularına tek bakışta erişilir. Bu, en düşük ağırlıklı kenarı seçmeyi kolaylaştırır.

init_graph() yaz. Komşuluk matrisini döndür. print(init_graph()) ile 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]]
print(init_graph())