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

  • Epic Tutorials for iPhone, iPad and iOS

    Epic Tutoria

    18 EYLÜL 2011
  • LaKe Lightroom Tutorials

    LaKe Lightro

    22 Temmuz 2014
  • Makeup Lover

    Makeup Lover

    12 HAZİRAN 2011

İLGİLİ SORU / CEVAPLAR