Kruskal Algoritması ile Minumum Yayılan Ağaç Problemi Çözümü(Örnek Problem)

Kruskal Algoritması ile Minumum Yayılan Ağaç Problemi Çözümü

Problem:

Ankara’ya turistik yerleri gezmek için arabayla gelen bir turist,gezeceği yerler olan Anıtkabir,Etnografya Müzesi,Gençlik Parkı,Roma Hamamı, Hacı Bayram ve Anadolu Medeniyetler Müzesi’nin içinde bulunduğu alanın bir krokisini çıkarmıştır.Fazla parası olmayan bu turistimiz oluşturduğu krokideki tüm adresleri gezmek istemektedir.Bu turistimiz belirlediği adresleri en kısa mesafede yani en az maliyetle nasıl gezebilir?(Bu turistin kullandığı yolu tekrar kullanmama zorunluluğu yoktur.)

*Turist tarafından krokisi çıkarılan yerlerin şebeke haline getirilmesi

Graf Algoritmaları ve Birbirlerinden Farkları

1-) Kruskal Algoritması: Daha az maliyetli kenarları tek tek değerlendirerek yol ağacını bulmaya çalışır. Ara işlemler birden çok ağaç oluşturabilir.

2-) Prim Algoritması: En az maliyetli kenardan başlayıp onun uçlarından en az maliyetle genişleyecek kenarın seçilmesine dayanır. Bir tane ağaç oluşur.

3-) Dijkstra Algoritması: Ağırlıklı ve yönlü graflar için geliştirilmiştir ve graf üzerindeki kenarların ağırlıkları 0 veya sıfırdan büyük sayılar olmalıdır.

 Negatif ağırlıklar için çalışmaz.

4-) Floyd Algoritması:Dijsktra gibi çalışır. Sürekli gidilen düğümde toplam maliyeti güncellemektedir. Düğümler ve yollar matrisleri oluşturulur. Velhasıl kullanımı zordur.

Çözüm:

Kullanımının kolay olması,iki yönlü olması,başlangıç düğümünün(noktasının) ilk olarak belirlenmemesi gibi etkenlerden dolayı bu problem için en uygun algoritmanın Kruskal Algoritması olmasına karar verilmiştir

                  .