28 Temmuz 2009, Salı
Kruskal vs Prim
Prim's algorithm ne zaman ve Kruskal's merak ettiğim minimum yayılan ağaç bulmak için? İkisi de kolay mantık aynı en kötü durumda, tek fark biraz farklı veri yapıları dahil uygulamasıdır. Belirleyici faktör nedir?
CEVAP
28 Temmuz 2009, Salı
Kenarları dolu bir grafik varsa, Prim algoritması kullanın.
Bir grafik içinVköşelerEkenarları, Kruskal algoritması çalışırO(E log V)zaman ve Prim algoritması çalıştırabilirsinizO(E V günlük V)Fibonacci Heap bir kullanırsanız itfa zaman,.
Prim algoritması köşeleri daha çok kenarları çok yoğun bir grafik var zaman sınırı içinde önemli ölçüde daha hızlıdır. Kruskal basit veri yapıları kullandığı için daha tipik durumlarda (seyrek grafikleri) gerçekleştirir.
Bunu Paylaş: