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

  • CareyHolzman

    CareyHolzman

    24 Ocak 2008
  • Jimmie Jones

    Jimmie Jones

    16 Kasım 2007
  • Shylo Sharity

    Shylo Sharit

    27 EKİM 2011

İLGİLİ SORU / CEVAPLAR