7 Şubat 2014

Prim Algoritması C#

Prims Algorithm in C#
Prim's Algorithm in C#

Prim algoritması bir graph(çizge) üzerinde verilen bir başlangıç noktaya göre en kısa ağaç yapısını oluşturan algoritmalardan biridir. 

Anlatıma başlamadan önce kodumuzu verelim
https://github.com/muhammedtanriverdi/Prims_Algorithm_C_Sharp/
(kodda eksiklikler hatalar ya da fazlalıklar varsa (ki vardır) affola)



Aşağıdaki örnek graph(çizge) üzerinde algoritmayı anlatalım. Aşağıdaki graphı ele aldığımızda kümemiz

S : A B C D E F G H

gibi ele alabiliriz.


Algoritmanın başlangıcı bütün vertexlerin uzunluğu(distance) sonsuz yapılır. 



Algoritma başlangıç için seçilen  Root vertex (başlangıç köşesi) üzerinden işleme başlanır ve uzunluğu 0(sıfır) yapılır. Başlangıç vertexi için A'yı seçelim.


Rengi kırmızı yapılarak işleme alındığı ifade edilir


İşlemde olan vertexin en kısa kenarı(edge) olan 3 alınır ve ailesi (parent) kırmızı vertex olduğu tutulur. Okun yönü ailesini gösteriyor. 

Buradaki işlem şu şekilde döngüye alınır; Seçili vertexe ait tüm yollar sırasıyla (küçükten büyüğe doğru) işleme alınır. Yani 3 ve 14 var. İlk olarak 3'ün işleme alınması. 3'ü işleme alındığında 
sonsuz >? 3 
doğru olduğundan dolayı 3'ü vertexin içine yazıyoruz (distance)


Sonraki işlem sonsuz > 14 olduğundan dolayı, vertexin uzunluğunu 14 yaparız ve ailesini ok ile gösteririr.


Başlangıç vertexinden başlamıştık ve 2 kenara sahipti ve 2 kenarını da işleme aldık ve kümeden çıkardık.
Kalan kümemizi küçükten büyüğe sıralıyoruz.

S : C B D E F G H



Küçükten büyüğe sıralıdığımızda 3, 14, sonsuz .... diye sıralanacaktır.
S : C B D E F G H

En küçük vertex olan 3 - C vertexini işleme alıyoruz. 
3 kenarı var ; 3, 8 ve 10
3'ten başlarız ve 3 <? 0 / sağlamadığı için A vertexinin içi değiştirilmez 0 olarak kalır
8 kenarını ele alırız, 8 <? sonsuz / evet sağladı, sonsuz yerine 8 yazılır ve parent'i gösterilir.


Düğer kenar 10 ele alınır, 10 <? 14 / evet sağladı, 14 yerine 10 yazılır ve parenti diğer taraftan silinip bu tarafa verilir.

B-3 vertexi de kümeden çıkarılır ve kalan küme tekrar sıralanıp en küçük vertex ele alınır.

S : B D E F G H
Sıralama yapıldıktan sonra
S : F B D E G H

F - 8 ile işlemlere devam edilir.
bu şekilde işlemler devam eder. S kümesinde eleman kalmayan kadar.


F kümeden çıkar.
S : E B H D G
(2, 10, 15, sonsuz, sonsuz)
Sıradaki vertex E-2

E kümeden çıkar.
S : D B G H 
(4, 5, 9, 15)
Sıradaki vertex D - 4

D kümeden çıkar.
S : B G H 
(5, 9, 15)
Sıradaki vertex B - 5
B kümeden çıkar.
S : G H 
(9, 15)
Sıradaki vertex G - 9
G kümeden çıkar.
S : H 
(15)
Sıradaki vertex H - 15

H kümeden çıkınca kümemiz boşalır ve prim algoritması uygulanmış olur.

Ağaç yapımız aşağıdaki şekildeki gibi oluşur.


Umarım yardımcı olabilmişimdir...

Hiç yorum yok:

Yorum Gönder

Bu Blogda Ara

İletişim

Ad

E-posta *

Mesaj *