Minimum çevreli ağaç
- Algoritmalar kursu
- İleri seviye
- Ders 37/56
- 4 dk
Bir graph'ın minimum çevreli ağacını bulma problemini öğrenirsin.
Minimum çevreli ağaç
Bir ağırlıklı grafta tüm düğümleri bağlayan ve toplam ağırlığı en küçük olan ağaca minimum çevreli ağaç (MST) denir. n düğümlü bir ağacın n-1 kenarı vardır.
Kruskal algoritması, kenarları ağırlığa göre sıralayıp döngü oluşturmayanları ekleyerek MST'yi bulur.
Kenar listesi
Kruskal kenar listesiyle çalışır. Her kenar (u, v, w) üçlüsüdür: u'dan v'ye, w ağırlığıyla. Graf yönsüzdür.
Beş kenarlı örnek grafta MST'yi bulacağız. Kenarlar sıralanmadan önce ham haliyle tanımlanır.
Uygulama init_edges fonksiyonu
init_edges() yaz. Kenar listesini döndür. print(init_edges()) ile yazdır.
Başlangıç kodu
def init_edges():
# Kenar listesini döndürÖrnek çözüm
def init_edges():
# Kenar listesini döndür
return [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
print(init_edges())Beklenen çıktı
[(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 4 düğümlü MST kaç kenar içerir?
- 3 Doğru cevap
- 2
- 4
- 5
Açıklama: n-1 = 4-1 = 3 kenar.
2 en küçük kenar
min_edge = (____, 3, 4)min_edge = (2, 3, 4)Açıklama: 2 doğru.
3 Minimum çevreli ağaç: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
(2,3,4) |
En küçük |
(0,3,5) |
İkinci |
(0,1,10) |
Dördüncü |
(1,3,15) |
En büyük |