PRİM ALGORİTMASI(MİNİMUM SPANNİNG TREE ALGORİTHM)

PRİM ALGORİTMASI MST

PRİM’S ALGORİTHMS ALGORİTMA ANALİZİ

Prim algoritması verilen bir grafda herhangi bir düğümden başlayarak diğer tüm düğümlerin dolaşılmasını sağlayan en kısa yol algoritmasıdır. (Minumum spanning tree) şimdi adım adım verilen bir graf üzerinde prim algoritması ile en kısa yolu bulalım.

1-Bu grafda A düğümden başlamayı tercih ettik ve A düğümün komşuları olan B,F ve D düğümlerinin A düğümüne olan uzaklıklarına baktık sırasıyla 2,6 ve 5 olduğunu gördük bu yüzden A düğümü en yakın komşusu B düğümüne gitti.

2.Adımda artık A ve B düğümlerinin tüm kenarlarına bakıyoruz sırası ile ;

(B,C)=8

(B.D)=6

(A,D)=5   => En kısa kenar olduğundan bunu seçiyoruz 

(A,F)=6

olduğundan en kısa kenar olan (A,D)=5 yolunu tercih ederiz.

3.adımda (D,C)=3 yolunu seçiyoruz

4.adımda (C,E)=5 yolunu seçiyoruz

ve son olarak 5.adımda (E,F)=2 yolu seçilerek A,B,C,D,E,F düğümlerinin hepsi en kısa yoldan prim algoritması ile dolaşıldı şimdi minumum yolu hesaplayalım;

Minumum yol=>  2+5+3+5+2 = 17  çıkar.

Hepinize kolay gelsin iyi çalışmalar…

 

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir