Prim mantığı
- Algoritmalar kursu
- İleri seviye
- Ders 41/56
- 4 dk
Bir düğümden başlayıp her adımda en ucuz kenarı ekleyen algoritmayı öğrenirsin.
Prim mantığı
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.
Uygulama init_graph fonksiyonu
init_graph() yaz. Komşuluk matrisini döndür. print(init_graph()) ile yazdır.
Başlangıç kodu
def init_graph():
# Komşuluk matrisini döndürÖrnek çözüm
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())Beklenen çıktı
[[0, 10, 6, 5], [10, 0, 0, 15], [6, 0, 0, 4], [5, 15, 4, 0]]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Prim nasıl başlar?
- Tek düğümden Doğru cevap
- Tüm kenarlardan
- En uzun yoldan
- Döngüden
Açıklama: Prim tek bir düğümden başlar.
2 kenar ağırlığı
graph[0][1] = ____graph[0][1] = 10Açıklama: 10 doğru.
3 Prim mantığı: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
graph[0][1] |
10 |
graph[0][2] |
6 |
graph[0][3] |
5 |
graph[2][3] |
4 |