dapHne
14-12-05, 22:29
Prim Algortiması, bir graf üzerinde minimum örten ağacı bulmak için kullanılan algoritmalardan birisidir. Algoritmayı şu şekilde açıklayabiliriz:
Başlangıçta, herhangi noktayı ağacı oluşturmaya başlamak için seç.
Oluşturulan ağaca eklemek için, şu ana kadar oluşturulmuş ağaç üzerinden erişilebilen ve daha önceden ağaca katılmamış olan en küçük ağırlıklı ayrıtı seç.
Eğer bu ayrıtın ağaca katılması, bir çevre oluşmasına sebep olmuyorsa, ağaca ekle.
Ağaçtaki ayrıt sayısı (N-1)'e ulaşana kadar ikinci adıma geri dön.
Aşağıda Prim Algoritmanın C++ dilinde yazılmış kaynak kodu gözükmektedir.
#include <algorithm>
#include <iostream>
#include <vector>
#include <list>
using namespace std;
//-----------------------------------------------------------------------
//
// Grafta bulunan ayrıt, her iki ucundan da bir düğüme bağlıdır. Bu
// düğümlerin numaraları d1 ve d2'dir. ayrıtın ağırlığı ise w'dir.
// Ayrıca ayrıtın minimum örten ağaç içinde bulunup bulunmadığını
// anlamak için bir adet lojik değişken kullanılmıştır.
//
//-----------------------------------------------------------------------
struct ayrit
{
bool kullanimda;
int w;
int d1;
int d2;
// ayrit sınıfı için yapıcı.
ayrit (int id1, int id2, int agirlik) : d1 (id1), d2 (id2), w (agirlik)
{
kullanimda = false; // ayrıt ilk başta ağaca dahil değil
}
};
//------------------------------ prim -----------------------------------
//
// Amaç : Verilen grafın minimum kapsayan ağacını bulmak
//
// Giriş parametresi : Üzerinde çalışılan graf
//
// Dönüş değeri : Minimum örten ağaca ait ayrıtları tutan vektör
//
// Fonksiyonda minimum örten ağacı bulma işlemi, prim algoritması ile
// gerçeklenmiştir.
//
//-----------------------------------------------------------------------
vector<ayrit> prim (vector<ayrit>& G)
{
vector<ayrit> S; // Sonucu tutmak için
list<int> D; // Graftaki düğümlerin numaralarını tutmak için
// Graf üzerindeki düğümler listeye ekleniyor
for (int i = 0; i < G.size (); i ++)
{
D.push_back (G[i].d1);
D.push_back (G[i].d2);
}
// Aynı numaraya sahip olanlar listeden çıkarılıyor
D.sort ();
D.unique ();
// Minimum örten ağacı oluşturmaya başlamak için bir düğüm seçiliyor.
// Ağaç bu düğümden başlayarak genişleyecek.
D.remove (G[0].d1);
while (1)
{
// while döngüsünün her dönüşünde, ağaca eklenebilecek durumda
// olan ayrıtlardan, minimum ağırlıkta olanı araştırılıyor.
int min = RAND_MAX;
int ayritNo = -1;
// Graftaki tüm ayrıtlara tek tek bak
for (i = 0; i < G.size (); i ++)
{
// Bu ayrıt kullanımda mı?
if (!G[i].kullanimda)
{
// Bu ayrıt daha önce ağaca eklemek için bulduğum uygun
// ayrıta göre daha mı hafif?
if (G[i].w < min)
{
// Bu ayrıtın her iki ucundaki düğüm de daha önce ağaca
// eklenmiş düğümlerin uçlarıysa, bu ayrıtı ağaca
// eklediğimizde bir çevre oluşturacaktır. Bu yüzden
// böyle bir ayrıtı ağaca eklememek gerekiyor.
// Buradaki D vektörü henüz hiç kullanılmamış düğümleri
// tutar. Eğer bir düğüm minimum örten ağaç içinde
// kullanılırsa, o düğüm bu vektörden silinir.
// Aşağıdaki ifler ile, eklemek istediğimiz ayrıtın iki
// ucundaki düğümlerden sadece birinin daha önceden
// kullanılmış olup olmadığı araştırılıyor. Böyle olunca,
// hem bu ayrıt ile mevcut ağaç arasında bir bağlantı
// olmuş olur, hem de eklenince çevre oluşturmaz.
int k = 0;
if (find (D.begin (), D.end (), G[i].d1) == D.end ()) k ++;
if (find (D.begin (), D.end (), G[i].d2) == D.end ()) k ++;
if (k == 1)
{
min = G[i].w;
ayritNo = i;
}
}
}
}
// Eğer eklenecek ayrıt kalmadıyda, fonksiyonu sonlandir.
if (ayritNo == -1) return S;
// Bu ayrıt artık kullanılıyor. Bir daha eklemeye çalışma!
G[ayritNo].kullanimda = true;
// d1 ve d2 nolu düğümleri düğüm listesinden sil. Bu düğümler
// artık kullanılmış düğümler.
D.remove (G[ayritNo].d1);
D.remove (G[ayritNo].d2);
// Elde edilen ayrıtı ağaca ekle
S.push_back (G[ayritNo]);
}
return S;
}
//------------------------------ main -----------------------------------
int main ()
{
vector<ayrit> S;
vector<ayrit> G;
// Graf oluşturuluyor.
G.push_back (ayrit (1, 2, 2));
G.push_back (ayrit (1, 3, 1));
G.push_back (ayrit (2, 3, 3));
G.push_back (ayrit (2, 4, 3));
G.push_back (ayrit (3, 4, 6));
G.push_back (ayrit (4, 5, 2));
S = prim (G);
return 0;
}
Başlangıçta, herhangi noktayı ağacı oluşturmaya başlamak için seç.
Oluşturulan ağaca eklemek için, şu ana kadar oluşturulmuş ağaç üzerinden erişilebilen ve daha önceden ağaca katılmamış olan en küçük ağırlıklı ayrıtı seç.
Eğer bu ayrıtın ağaca katılması, bir çevre oluşmasına sebep olmuyorsa, ağaca ekle.
Ağaçtaki ayrıt sayısı (N-1)'e ulaşana kadar ikinci adıma geri dön.
Aşağıda Prim Algoritmanın C++ dilinde yazılmış kaynak kodu gözükmektedir.
#include <algorithm>
#include <iostream>
#include <vector>
#include <list>
using namespace std;
//-----------------------------------------------------------------------
//
// Grafta bulunan ayrıt, her iki ucundan da bir düğüme bağlıdır. Bu
// düğümlerin numaraları d1 ve d2'dir. ayrıtın ağırlığı ise w'dir.
// Ayrıca ayrıtın minimum örten ağaç içinde bulunup bulunmadığını
// anlamak için bir adet lojik değişken kullanılmıştır.
//
//-----------------------------------------------------------------------
struct ayrit
{
bool kullanimda;
int w;
int d1;
int d2;
// ayrit sınıfı için yapıcı.
ayrit (int id1, int id2, int agirlik) : d1 (id1), d2 (id2), w (agirlik)
{
kullanimda = false; // ayrıt ilk başta ağaca dahil değil
}
};
//------------------------------ prim -----------------------------------
//
// Amaç : Verilen grafın minimum kapsayan ağacını bulmak
//
// Giriş parametresi : Üzerinde çalışılan graf
//
// Dönüş değeri : Minimum örten ağaca ait ayrıtları tutan vektör
//
// Fonksiyonda minimum örten ağacı bulma işlemi, prim algoritması ile
// gerçeklenmiştir.
//
//-----------------------------------------------------------------------
vector<ayrit> prim (vector<ayrit>& G)
{
vector<ayrit> S; // Sonucu tutmak için
list<int> D; // Graftaki düğümlerin numaralarını tutmak için
// Graf üzerindeki düğümler listeye ekleniyor
for (int i = 0; i < G.size (); i ++)
{
D.push_back (G[i].d1);
D.push_back (G[i].d2);
}
// Aynı numaraya sahip olanlar listeden çıkarılıyor
D.sort ();
D.unique ();
// Minimum örten ağacı oluşturmaya başlamak için bir düğüm seçiliyor.
// Ağaç bu düğümden başlayarak genişleyecek.
D.remove (G[0].d1);
while (1)
{
// while döngüsünün her dönüşünde, ağaca eklenebilecek durumda
// olan ayrıtlardan, minimum ağırlıkta olanı araştırılıyor.
int min = RAND_MAX;
int ayritNo = -1;
// Graftaki tüm ayrıtlara tek tek bak
for (i = 0; i < G.size (); i ++)
{
// Bu ayrıt kullanımda mı?
if (!G[i].kullanimda)
{
// Bu ayrıt daha önce ağaca eklemek için bulduğum uygun
// ayrıta göre daha mı hafif?
if (G[i].w < min)
{
// Bu ayrıtın her iki ucundaki düğüm de daha önce ağaca
// eklenmiş düğümlerin uçlarıysa, bu ayrıtı ağaca
// eklediğimizde bir çevre oluşturacaktır. Bu yüzden
// böyle bir ayrıtı ağaca eklememek gerekiyor.
// Buradaki D vektörü henüz hiç kullanılmamış düğümleri
// tutar. Eğer bir düğüm minimum örten ağaç içinde
// kullanılırsa, o düğüm bu vektörden silinir.
// Aşağıdaki ifler ile, eklemek istediğimiz ayrıtın iki
// ucundaki düğümlerden sadece birinin daha önceden
// kullanılmış olup olmadığı araştırılıyor. Böyle olunca,
// hem bu ayrıt ile mevcut ağaç arasında bir bağlantı
// olmuş olur, hem de eklenince çevre oluşturmaz.
int k = 0;
if (find (D.begin (), D.end (), G[i].d1) == D.end ()) k ++;
if (find (D.begin (), D.end (), G[i].d2) == D.end ()) k ++;
if (k == 1)
{
min = G[i].w;
ayritNo = i;
}
}
}
}
// Eğer eklenecek ayrıt kalmadıyda, fonksiyonu sonlandir.
if (ayritNo == -1) return S;
// Bu ayrıt artık kullanılıyor. Bir daha eklemeye çalışma!
G[ayritNo].kullanimda = true;
// d1 ve d2 nolu düğümleri düğüm listesinden sil. Bu düğümler
// artık kullanılmış düğümler.
D.remove (G[ayritNo].d1);
D.remove (G[ayritNo].d2);
// Elde edilen ayrıtı ağaca ekle
S.push_back (G[ayritNo]);
}
return S;
}
//------------------------------ main -----------------------------------
int main ()
{
vector<ayrit> S;
vector<ayrit> G;
// Graf oluşturuluyor.
G.push_back (ayrit (1, 2, 2));
G.push_back (ayrit (1, 3, 1));
G.push_back (ayrit (2, 3, 3));
G.push_back (ayrit (2, 4, 3));
G.push_back (ayrit (3, 4, 6));
G.push_back (ayrit (4, 5, 2));
S = prim (G);
return 0;
}