Olası Çoğalt:
Kruskal vs Primkrukshal'ın algoritması veya minimum yayılma ağacını bulmakta daha iyi olan Prims Algoritması?
krukshal algoritması veya Prims Algoritma hangisinin minimum yayılan ağaç bulmakta iyidir?
Bahsediğim görmediğim Prim algoritması lehine bir puan ekleyeceğim. Eğer N noktaları ve x ile y arasındaki mesafe için bir mesafe fonksiyonu d (x, y) verilirse, Prim'in algoritmasını uzay O (N) (fakat N^2) kullanarak gerçekleştirebilirsiniz.
A'dan rasgele bir nokta ile başlayın ve A'dan diğer tüm noktalara olan mesafeleri gösteren bir N-1 boyutu dizisi oluşturun. Yayılma ağacında A ve B bağlantılarını en kısa mesafeyle ilişkilendiren B'yi seçin ve ardından dizideki mesafeleri, diğer noktaya kadar belirtilen mesafenin minimum değeri ve B'den diğer uzaklığa kadar olan mesafeyi en az olacak şekilde güncelleyin. en kısa bağlantının B'den nereden geldiğini ve A noktasından nereye gittiğini not edin.
Kruskal'ın bir uzaklık fonksiyonu tarafından belirlenen yoğun bir grafik için algoritmasını kullanmanın benzer bir yolunu bilmiyorum ve büyük N için zamanın sabrından kaçmadan önce O (N^2) alanı bitebilirsiniz O (N^2).
@Adnan: bunun ev ödevi olduğunu nereden biliyorsunuz? –
http://stackoverflow.com/questions/1195872/kruskal-vs-prim – Eric
Birkaç yıl öncesine ait algoritma analizleri sınıfına çok aşina geliyor. – Adnan