Araçlar / Graf & Rota
Minimum Yayılan Ağaç (MST) Çözücü
Yönsüz ağırlıklı bir ağdaki tüm düğümleri birbirine bağlayan en az toplam ağırlıklı ağacı bul. Prim (binary heap) bir düğümden büyütür; Kruskal (union-find) global sıralama yapar. Graf bağlı değilse minimum yayılan orman (forest) döner. Rehbere git →
MST toplam ağırlığı
Ağaç kenarları — eklenme sırasıyla
Prim her adımda mevcut ağaca en ucuz şekilde komşu yeni düğümü ekler. Kruskal kenarları küresel olarak sıralayıp çevrim üretmeyenleri katar.
| Adım | Kenar | Ağırlık | Birikimli |
|---|
Düğüm bileşenleri
Aynı bileşen kimliğine sahip düğümler MST'de (ya da orman ise aynı ağaçta) birbirine bağlı.
| Düğüm | Bileşen |
|---|
Konuyu derinleştir
Prim, Kruskal ve minimum yayılan ağaç teorisi
Cut property ve cycle property, açgözlü algoritmaların neden MST'yi doğru bulduğu, union-find karmaşıklığı, bağlı olmayan graflar (orman), ağ tasarımı / kümeleme / yaklaşım algoritmaları uygulamaları ve sayısal örnekler.
Rehberi oku →