Minimum çevreli ağaç

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.

Örnek çözümü göster

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())

Kendini test et

4 düğümlü MST kaç kenar içerir?
- 3
- 2
- 4
- 5
Cevabı göster

3 — n-1 = 4-1 = 3 kenar.

en küçük kenar

min_edge = (____, 3, 4)

Cevabı göster

min_edge = (2, 3, 4)

Minimum çevreli ağaç: kavramları eşleştir

(2,3,4)

En küçük
(0,3,5)

İkinci
(0,1,10)

Dördüncü
(1,3,15)

En büyük

Sıradaki ders: Kenar sıralama

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler