Kruskal Algoritması

Kruskal Algoritması ile bir G grafı içinde olması halinde minimum spanning tree (minimum kapsama ağacı) bulunur. Asıl amaç bir graf üzerinde en kısa yoldan döngü oluşturmayacak şekilde tüm düğüm noktalarına ulaşabilmek.

Kruskal algoritmasını kullanarak MST (minimum spanning tree) bulma adımları aşağıdaki gibidir.

  1. Kenar uzunlukları küçükten büyüğe doğru olacak şekilde alt alta sıralanır.
  2. En Küçük kenardan seçilir, graf içinde döngü oluşturup oluşturmadığı kontrol edilir. Eğer döngü oluşmuyorsa, kenar dahil edilir. Fakat bir döngü oluşuyorsa o kenar kullanılmaz.
  3. (N-1) kadar kenar sayısı elde edilene kadar 2. adım tekrarlanır.
Not: N sayısı verilen grafın köşe sayısıdır. (N-1) ise minimum kapsama ağacının (MST) kenar sayısıdır.

Kruskal algoritmasını örnek bir graf üzerinde uygulayalım.

İlk olarak grafın kenar uzunluklarına göre küçükten büyüğe kenarlar alt alta sıralanır.


Daha sonrasında en küçük kenarlardan herhangi bir tanesi seçilir. Örnek üzerinde ilk olarak b-f seçilmiştir ama farklı bir kenar seçimi (e-ı) sonucu etkilemeyecektir. b-f kenarı ağaca (MST) dahil edilir.


b-f kenarından sonra en küçük bir diğer kenar olan e-ı kenarı seçilir ve ağaca (MST) dahil edilir. Kullanılan kenarları bir daha kullanmıyoruz.


Kalan kenarlarımız arasında yine en kısa herhangi bir kenarı seçiyoruz. a-b kenarı seçiliyor ve döngü olmuyorsa ağaca (MST) dahil edilir.


g-ı kenarı seçilir, döngü olmuyorsa ağaca (MST) dahil edilir.


c-h kenarı seçilir, döngü olmuyorsa ağaca (MST) dahil edilir.


e-f kenarı seçilir, döngü olmuyorsa ağaca (MST) dahil edilir.


a-c kenarı seçilir, döngü olmuyorsa ağaca (MST) dahil edilir.


Bu kez b-e kenarı seçilir. Ancak b-e kenarı ağaca dahil edilirse yeşil daire içinde görüldüğü gibi döngü olacaktır. Bu nedenle b-e kenarı kullanılmaz.


f-g kenarı seçilir, ancak kenar yeşil dairede görüldüğü gibi döngüye sebep oluyor. Bu yüzden f-g kenarı kullanılmaz.


c-d kenarı seçilir, döngü oluşmuyorsa ağaca (MST) dahil edilir. Görüldüğü gibi tüm düğüm noktalarına ulaşmış olduk. Graf köşe sayısı 9 ve MST kenar sayımız ise 8. Tüm düğümleri dolaşan en kısa yol uzunluğu: 2+3+2+4+1+3+1+2=18.




Hiç yorum yok:

Yorum Gönderme