Kruskal algoritması, bir grafın tüm düğümlerinin en kısa şekilde dolaşılmasını amaçlar.
Her seferinde en iyi kenarın seçilmesi esasına dayalıdır. n kenarlı bir graf için herhangi bir düğümle başlanır ve en kısa yol buna eklenir. Döngü oluşturmayacak şekilde (n-1) kenar eklenene kadar devam edilir. Aynı değerli kenarlarda seçim keyfi yapılabilir. Düğümlerin birleştirilme işlemine en az maliyetli kenardan başlanır, kalan kenarlar arasından en az maliyetlisi seçilerek devam edilir.
Bir örnek üzerinde bu algoritmayı uygulayalım:
Her seferinde en iyi kenarın seçilmesi esasına dayalıdır. n kenarlı bir graf için herhangi bir düğümle başlanır ve en kısa yol buna eklenir. Döngü oluşturmayacak şekilde (n-1) kenar eklenene kadar devam edilir. Aynı değerli kenarlarda seçim keyfi yapılabilir. Düğümlerin birleştirilme işlemine en az maliyetli kenardan başlanır, kalan kenarlar arasından en az maliyetlisi seçilerek devam edilir.
Bir örnek üzerinde bu algoritmayı uygulayalım:
__________________________________________________________________________
* Orijinal graf aşağıdaki gibi olsun:
__________________________________________________________________________
* Algoritmada önce en kısa kenarlar belirlenir. Ve uygun olan seçilir. Aynı uzunlukta kenarlar varsa rasgele seçim yapılır. Yukarıdaki şekilde de görüldüğü gibi AD ve CE kenarları eşit uzunluklara sahip en kısa kenarlardır. Bunlardan AD gelişigüzel seçilebilir. Seçim aşağıda yeşil renk ile belirtilmiştir:
__________________________________________________________________________
* AD seçildikten sonra kalan kenarlar arasında, bir döngü oluşturmayacak şekilde seçilebilecek en kısa kenar CE kenarıdır. Bu nedenle bir sonraki seçim bu kenar olacaktır:
__________________________________________________________________________
* Kalan kenarlar incelendiğinde, en kısa olan kenarın, 6 birim uzunluğu ile DF olduğu görülmektedir. Ayrıca herhangi bir çevrim de oluşturmamaktadır. Bu nedenle yeni seçim bu kenar olacaktır:
__________________________________________________________________________
* Geriye kalan kenarlar tekrar incelendiğinde, kalan en kısa kenarların 7 birim uzunluğu ile AB ve BE olduğu görülmektedir. Bunlardan AB kenarı seçilebilir:
AB kenarı seçildikten sonra, şekil incelendiğinde artık BD kenarının kullanılamayacağı görülür. Çünkü sonraki adımlarda BD kenarı seçilirse ABD bir çevrim oluşturmaktadır. Kruskal algoritmasının şartlarından biri de seçimlerin bir çevrim, döngü oluşturmamasını gerektirmektedir. Bu nedenle bu kenar kırmızı ile belirtilmiştir.
__________________________________________________________________________
* Şekil incelendiğinde, en kısa kenarın BE kenarı olduğu görülmektedir:
BE kenarı seçildikten sonra, BC, DE, ve FE kenarlarının da, birer çevrim oluşturabileceği görülmektedir. Bu nedenle bu kenarlar da ilerleyen adımlarda kullanılamayacaktır.
__________________________________________________________________________
* Geriye sadece EG ve FG kenarları kalmaktadır. Bu kenarlardan en kısa olan, 9 birim uzunluğundaki EG seçilir.
__________________________________________________________________________
* Seçilebilecek kenar kalmamıştır. İşlem sona erer.
__________________________________________________________________________
Kaynaklar:
__________________________________________________________________________
Hiç yorum yok :
Yorum Gönder