^{Kruskal Algoritması}

^{Herkese merhabalar;}

^{Yazıya başlamadan önce minimum spanning tree adlı yazımızı incelemenizde fayda var.}

^Giriş

^{Bağlı ve yönsüz bir graf verildiğinde,bu grafın spanning tree(yayılan ağacı) ifade etmek için, tüm köşeleri birbirine bağlayan alt graf şeklinde bir tanım yapabiliriz.Tek grafın birden fazla farklı alt grafları yani spanning tree leri olabilir.Ağırlık,yönsüz,bağlantılı bir grafik için minimum spanning tree veya minimum ağırlıklı spanning tree,ağırlığı diğer her yayılan ağaçın ağırlığından daha az veya ona eşit olan bir yayılan ağaçtır.Yayılan bir ağacın ağırlığı,yayılan ağacın her bir kenarına verilen ağırlıkların toplamıdır.Bir minimum yayılan ağaçın kaç kenarı vardır? Sorusuna cevap verecek olursak MST v-1 kenarlara sahip olan bir graf düşünelim.Burada v verilen graftaki köşe sayısıdır.}

^{Adım Adım Algoritmayı Çalıştıralım}

^{MST algoritmasını adım adım inceleyecek olursak;}

^{1.Adımda:Tüm kenarları ağırlıklarına göre azalmayacak şekilde yani artan şekilde sıralayın.}

^{2.Adımda:En küçük kenarları seçin ve şimdiye kadar oluşan alt graf ile bir döngü oluşturmadığına dikkat edit.Döngü oluşmaması durumunda bu kenarı yeni grafa ekleyin eğer döngü oluşturuyorsa bu kenarı atın.}

^{3.Adımda: Alt graf (V-1) kenarlar oluşana kadar 2. Adımı tekrar çalıştırın.}

^{Özet olarak;}

^{Bir graf verilsin.Bu grafın tüm kenarları ağırlıklarına göre listeleyin daha sonra en küçükten, en büyüğe doğru komşulukları işaretleyin(Ben sınavlarda bu işlemi verilen grafın üzerinden farklı renkte çizgi çekerek çalışıyorum.) şimdi işaretlediğimiz çizgide hiçbir döngü olmuyacak şekilde çizimi yaptıktan sonra gereksiz alanlar bulunur ve graftan atılır orjinal grafta çizdiğimiz kenarlar neticesinde yeni bir grafımız olur buda spanning tree olarak adlandırılabilir.}

Özet

• En Kısa yolu bulma algoritmasıdır.

• Edge'ler üzerinden,kenarlarda çalışır.

• Kenarları sıralayarak başlıyoruz.(x-y =1 , z-k = 2)

• Edge listesi oluşturuluyor küçükten büyüğe doğru sıralanıyor.

• Visited ve unvisited kümeleri var. 2 edge visited ise bunu  o edge çıkartılır.

• En sonda min. spaninng tree bütün düğümleri en az maliyetli dolaşır.(Algoritmanın genel amacıda budur.)

^Son

^{Diğer yazımıda bu algoritma ile ilgili bir örnek çözeceğiz.}

^{Herkese iyi çalışmalar.}