Bu konunun görsel anlatımı eklenmiştir:

Yazan: Şadi Evren ŞEKER

Bir asgari tarama ağacı (minimum spanning tree) algoritması olan Prim algoritması, işaretlemiş olduğu komşuluklara en yakın düğümü bünyesine katarak ilerler. Buna göre aşağıdaki grafiğin asgari tarama ağacını çıkaralım:

asgari tarama ağacı için örnek grafik

Yukarıdaki grafikte her düğüm için bir temsili harf ve her bağlantı için bir ağırlık değeri atanmıştır. Buna göre her düğümden diğerine gitmenin maliyeti belirlenmiştir.

Prim algoritmasında rasgele bir başlangıç noktası seçilir. Örneğin bizim başlangıç noktamız “z” düğümü olsun. Bu durumda ilk inceleyeceğimiz komşuluk, “z” düğümünden gidilebilen düğümler ve maliyetleri olacaktır.

z düğümünden gidilebilen düğümler ve maliyetleri aşağıda listelenmiştir:

y:5
t:10

Prim algoritması bu listedeki en küçük maliyetli komşuyu bünyesine dahil eder. Buna göre yeni üyelerimiz {z,y} olacaktır ve gidilen yollar {z-y:5} olacaktır. (ilk üyeler listesinde şimdiye kadar ziyaret edilmiş düğümler bulunur. Bu düğümler listesinde zaten olan bir düğüm listeye eklenemez. yollar listesinde ise hangi düğümden hangi düğüme ne kadar maliyetle gidildiği tutulur.) Dolayısıyla grafiğimizde Prim algoritması tarafından işaretlenen düğümler aşağıda gösterilmiştir:
prims1

şimdi üyelerimizin durduğu listedeki bütün düğümlerin komşularını listeleyelim:
t:5
t:10
v:4
x:3

yukarıdaki listede t düğümüne iki farklı gidiş bulunmaktadır ( hem z hem de y üzerinden). Biz algoritmamıza devam edip en küçük yolu bünyemize dahil edelim. En yakın komşu x:3’tür. Bu durumda üyelerimiz {z,y,x} olacak ve yollarımız {z-y:5,y-x:3} olacaktır. Bu durum aşağıdaki grafikte gösterilmiştir:
prims2

Yeniden komşularımızı listelersek:
t:5
v:1
w:2

yukarıdaki listede bünyemize aldığımız adadan, bir düğüme giden birden fazla yol bulunması durumunda en kısası alınmıştır. Bu durumda listenin en küçük elemanı olan v:1 tercih edilir ve üyelerimiz {z,y,x,v} yollarımız ise {z-y:5,y-x:3,x-v:1} olur. Durum aşağıdaki grafikte gösterilmiştir:

 

prims3

Yeniden komşularımızı listelersek:
t:5
u:3
w:1

yukarıdaki listede bünyemize aldığımız adadan, bir düğüme giden birden fazla yol bulunması durumunda en kısası alınmıştır. Bu durumda listenin en küçük elemanı olan w:1 tercih edilir ve üyelerimiz {z,y,x,v,w} yollarımız ise {z-y:5,y-x:3,x-v:1,v-w:1} olur. Durum aşağıdaki grafikte gösterilmiştir:

 

prims4

Yeniden komşularımızı listelersek:
t:5
u:1

yukarıdaki listede bünyemize aldığımız adadan, bir düğüme giden birden fazla yol bulunması durumunda en kısası alınmıştır. Bu durumda listenin en küçük elemanı olan u:1 tercih edilir ve üyelerimiz {z,y,x,v,w,u} yollarımız ise {z-y:5,y-x:3,x-v:1,v-w:1,w-u:1} olur. Durum aşağıdaki grafikte gösterilmiştir:

prims5

 

Yeniden komşularımızı listelersek:
t:3
s:2

yukarıdaki listede bünyemize aldığımız adadan, bir düğüme giden birden fazla yol bulunması durumunda en kısası alınmıştır. Bu durumda listenin en küçük elemanı olan s:2 tercih edilir ve üyelerimiz {z,y,x,v,w,u,s} yollarımız ise {z-y:5,y-x:3,x-v:1,v-w:1,w-u:1,u-s:2} olur. Durum aşağıdaki grafikte gösterilmiştir:

prims6

Son komşumuz olan t için en kısa ulaşım
t:3 değeridir ve u üzerinden sağlanır. Bu durumda listenin en küçük elemanı olan t:3 tercih edilir ve üyelerimiz {z,y,x,v,w,u,s,t} yollarımız ise {z-y:5,y-x:3,x-v:1,v-w:1,w-u:1,u-s:2,u-t:3} olur. Sonuçta elde edilen asgari tarama ağacı aşağıda verilmiştir:

prims7

Yorumlar

  1. coder

    hocam baştan 4. şekil yanlış çizilmiş, 4 br uzunluktaki çizgi çizilmiş 1 olacak. Anlatım için yine de teşekkrler bayağı faydalı 🙂

Bir Cevap Yazın

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


− 5 = bir