SORU
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ş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • Joshua Kywn

    Joshua Kywn

    17 Mayıs 2010
  • Michael Neal

    Michael Neal

    2 Mayıs 2009
  • SavageLuxxxGaming - Daily NBA 2K15 & NBA Live 15 Enjoy And Subscribe!

    SavageLuxxxG

    11 Ocak 2013

İLGİLİ SORU / CEVAPLAR