|
| Prims Algoritması |
#include <stdio.h> #include <limits.h>
#include <stdbool.h>
// Ağaç yapısındaki boyutu belirtiyorum
#define V 5
// En kısa yolu bulan fonksiyon, eğer daha kısa yol varsa güncelleme yapıyor.
int minKey(int key[], bool mstSet[])
{
// min değişkenine sonsuz değeri atandı.
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
// Asgari tarama ağacını ekrana bastıran fonksiyon
int printMST(int parent[], int n, int graph[V][V])
{
printf("Edge Weight\n");
for (int i = 1; i < V; i++)
printf("%d - %d %d \n", parent[i], i, graph[i][parent[i]]);
}
// MST yapısını create eden fonksiyon. Bu fonksiyona gönderilen graf parametresi sayesinde ağaç MST oluşturulur
void primMST(int graph[V][V])
{
int parent[V]; // yapılandırılmış MST'yi tutan değişken
int key[V]; // En az maliyeti tutan dizi
bool mstSet[V]; // bir düğümün ziyaret edilip edilmediğini kontrol eder
// Başlangıçta tüm düğümlerin maliyeti sonsuz kabul edilir.
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
// Her zaman ilk vertex MST'ye dahil edilir.
key[0] = 0; // ilk düğümün maliyeti 0 kabul edilir
parent[0] = -1; // prims algoritmasında ilk düğüm her zaman kök düğümdür
// For döngüsüyle tüm düğümleri en kısa maliyetle gezmeyi hedefliyoruz
for (int count = 0; count < V-1; count++)
{
// key değerine en yakın maliyetli düğümü u değişkenine atıyoruz.
int u = minKey(key, mstSet);
// u indisini ziyaret edildi kabul ediyoruz
mstSet[u] = true;
// Burada key değişkenini ve parent değişkenini güncelliyoruz
for (int v = 0; v < V; v++)
// graph[u][v] noktası eğer 1 ise ve
// mstSet[v] değeri false ise ve
// graph[u][v] değeri key[v] değerinden küçükse parent ve key değerlerini güncelliyoruz.
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
// Yapılandırılmış MST'yi ekrana bastırıyoruz.
printMST(parent, V, graph);
}
// programı buradan test edebilirsiniz.
int main()
{
/* aşağıdaki yapı gibi bir graf oluşturmak istersek
2 3
(0)--(1)--(2)
| / \ |
6| 8/ \5 |7
| / \ |
(3)-------(4)
9 */
int graph[V][V] = {{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0},
};
// çözümü ekrana bastıran fonksiyon
primMST(graph);
return 0;
}
Etiketler: Min key fonksiyonu, Prims algoritması c kodu, prims asgari tarama ağacı