Merhabalar bu yazımda algoritma analizinde,problem çözmede,network topolojilerinde daha bir çok alanda kullanılan prim’s algoritmasından bahsediyor olacağım alt konulardan bu yazıda pek bahsetmeyeceğim ve bildiğinizi varsayacağım ki uzamasın. Prim’s algoritması nedir öncelikle bu kısmı halledelim. Prim’s algoritması elimizdeki bir graf’ın alt graf’ını (buna ağaç diyeceğiz) oluşturulabilecek en düşük maliyetle oluşturmayı hedeflemekte ve bize bu düşük maliyetli subgraph’ı oluştururken bir yol göstermekte. Sözel olarak açıklamam gerekirse algoritma şöyle işliyor; bize bir graph veriliyor, ardından ilk köşeyi alıyoruz, bu köşedeki yolların hangisinde daha az maliyet varsa o yolu seçip diğer köşeye gidiyoruz, aynı şekilde devam ediyoruz ve ilk geçtiğimiz köşelere gelene kadar devam ediyoruz. İlk tree seçimi bittiyse ve yandaki köşeler kalmışsa, önceden geçtiğimiz köşelerden bağımsız olan köşelere geri dönüp yeniden az maliyetli yolları seçerek ilerliyoruz ta ki tüm köşelerden geçene kadar. Şimdi bir örneğe bakalım.
Başlangıç olarak 0 dan başladık,baktık ki daha sonra en az maliyetli yol 2 ve oraya gittik,sonraki adımda tek seçeneğimiz vardı ve devam ettikve 3 köşesine geldik.Bu köşede de 5<6 olduğu için 4 köşesine gittik ve ağacımızın bir kısmını tamamlamış olduk. Şimdi geriye döneceğiz ve burada diğerlerinin üstünden geçmememiz önemli bu nedenle yeniden 0’dan başlıyoruz ve tek seçenek olan 1 ile devam ediyoruz. 1 köşesindeyken 3<6 olduğu için 5 köşesine geldik. İlk olarak 5 ten 7 ye gideceğiz çünkü bu yolun maliyeti bizim için 2 ardından 7 köşesinden 9 a gideceğiz yine maliyete bakıyoruz tabi ve 2<4. Şimdi geçmediğimiz köşeler kaldı değil mi ? Sonraki adımda da diğer köşeleri tekrarlamamak şartı ile geriye gideceğiz ve 5 e dönüyoruz. 5’e geldiğimizde ilk yapacağımız şey 6’ya gitmek başka yolumuz yok. Sonra amacımız tüm köşeleri geçmek olduğu için 8’e gidiyoruz. Burada asıl soru 4<5 ama biz 8’e gittik neden ? çünkü amacımız burada tüm köşelerden bir defa geçmekve biz daha önce 7’ye gelmiştik bu nedenle oradaki yolu kullanamıyoruz ve direk 8’e gidip treemizi bitiriyoruz.
Ekstra kaynak: https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/