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

  • Fubar Protocol

    Fubar Protoc

    21 AĞUSTOS 2010
  • Mr. H

    Mr. H

    1 Temmuz 2012
  • xSammyJoe1

    xSammyJoe1

    19 Temmuz 2011

İLGİLİ SORU / CEVAPLAR