Kruskal vs Prim
Bilgisayar biliminde, Prim'in ve Kruskal'ın algoritmaları, bağlı ağırlıklı bir yönsüz grafik için minimum yayılma ağacı bulan açgözlü bir algoritmadır. Yayılan ağaç, grafiğin her bir düğümü bir ağaç olan bir yolla bağlı olacak şekilde bir grafiğin alt grafiğidir. Her yayılan ağacın bir ağırlığı vardır ve tüm yayılan ağaçların olası minimum ağırlıkları/maliyeti minimum yayılan ağaçtır (MST).
Prim Algoritması hakkında daha fazla bilgi
Algoritma 1930'da Çek matematikçi Vojtěch Jarník tarafından ve daha sonra bağımsız olarak 1957'de bilgisayar bilimcisi Robert C. Prim tarafından geliştirildi. 1959'da Edsger Dijkstra tarafından yeniden keşfedildi. Algoritma üç temel adımda ifade edilebilir;
N düğümlü ve her bir kenarın ilgili ağırlığına sahip bağlı grafik göz önüne alındığında, 1. Grafikten rastgele bir düğüm seçin ve onu T ağacına ekleyin (bu ilk düğüm olacaktır)
2. Ağaçtaki düğümlere bağlı her bir kenarın ağırlıklarını göz önünde bulundurun ve minimumu seçin. T ağacının diğer ucundaki kenarı ve düğümü ekleyin ve kenarı grafikten çıkarın. (İki veya daha fazla minimum değer varsa herhangi birini seçin)
3. Ağaca n-1 kenar eklenene kadar 2. adımı tekrarlayın.
Bu yöntemde, ağaç tek bir rastgele düğümle başlar ve her döngüde o düğümden itibaren genişler. Bu nedenle, algoritmanın düzgün çalışması için grafiğin bağlantılı bir grafik olması gerekir. Prim algoritmasının temel biçimi, O(V2) zaman karmaşıklığına sahiptir.
Kruskal Algoritması hakkında daha fazla bilgi
Joseph Kruskal tarafından geliştirilen algoritma, 1956 yılında American Mathematical Society'nin tutanaklarında ortaya çıktı. Kruskal'ın algoritması da üç basit adımda ifade edilebilir.
n düğümü ve her bir kenarın ilgili ağırlığını içeren grafik göz önüne alındığında, 1. Tüm grafiğin en az ağırlığı olan yayı seçin ve ağaca ekleyin ve grafikten silin.
2. Geriye kalanlardan en az ağırlıklı kenarı bir döngü oluşturmayacak şekilde seçin. Ağacın kenarını ekleyin ve grafikten silin. (İki veya daha fazla minimum değer varsa herhangi birini seçin)
3. 2. adımdaki işlemi tekrarlayın.
Bu yöntemde algoritma en az ağırlıklı kenarla başlar ve her döngüde her kenarı seçmeye devam eder. Bu nedenle, algoritmada grafiğin bağlanmasına gerek yoktur. Kruskal'ın algoritması O(logV) zaman karmaşıklığına sahiptir
Kruskal's ve Prim's Algoritması arasındaki fark nedir?
• Prim'in algoritması bir düğümle başlatılırken Kruskal'ın algoritması bir kenar ile başlar.
• Prim'in algoritmaları bir düğümden diğerine uzanırken Kruskal'ın algoritması kenarları, kenarın konumu son adıma bağlı olmayacak şekilde seçer.
• Prim'in algoritmasında, Kruskal'ınki de bağlantısız grafiklerde çalışabilirken, grafiğin bağlantılı bir grafik olması gerekir.
• Prim'in algoritmasının zaman karmaşıklığı O(V2) ve Kruskal'ın zaman karmaşıklığı O(logV).
