1-) VERİYAPILARI - Prim asgari tarama ağacı Algoritması

            Prims algoritması ağırlıklı ve yönsüz grafda(weighted undirected graph) asgari tarama ağacını(minimum spanning tree) bulan bir aç gözlü algoritmadır(greedy algorithm).Prim algoritması, işaretlemiş olduğu komşuluklara en yakın düğümü bünyesine katarak ilerler.

Asgari tarama ağacı(Minimum Spanning Tree) nedir ?

Asgari tarama ağacı, grafdaki kenarları(edges) toplamda en düşük maliyeti oluşturacak ve tüm düğümleri(Vertices/Nodes) içerecek şekilde kullanarak üretilen bir ağaçtır(Tree).

KABA KOD:

ÖRN:

İlk Q={ A B C D E F}

1.  Adım

v=A   Q={ B C D E F}

u=B   d[u]>w[v,u] = Sonsuz > 2     

Sağlıyor

d[u]=2

 p[u]=A

u=C d[u]>w[v,u] = Sonsuz>1

Sağlıyor

d[u]=1

p[u]=A

2. Adım

v=C   Q={ B D E F}

u=D   d[u]>w[v,u] = Sonsuz >1    

Sağlıyor

 d[u]=1

 p[u]=C

u=F d[u]>w[v,u] = Sonsuz>2

Sağlıyor

d[u]=2

p[u]=C

u=A Kuyrukta yok

3. Adım

v=D  Q={B E F}

u=E   d[u]>w[v,u] = Sonsuz >7    

Sağlıyor

d[u]=7

p[u]=D

u=F d[u]>w[v,u] = 2>5

Sağlamıyor

4. Adım

v=B  Q={E F}

u=E   d[u]>w[v,u] = 7>2   

Sağlıyor

d[u]=2

p[u]=B

u=F d[u]>w[v,u] = 2>5

Sağlamıyor

5. Adım

v=E Q={F}

u=B Kuyrukta yok

u=D Kuyrukta yok

6. Adım

v=E  Q={ }    kuyruk boş olduğundan işlem bitiyor

Sonuç: