Bir önceki yazımızda BFS Algoritması konusuna değinmiş, adım adım nasıl gerçekleştirildiğini göstermiştik. Bu yazımızda ise algoritmanın nasıl c kodu olarak yazılabileceğini göstereceğiz.
Her şeyden önce şunu belirtmek lazım, BFS algoritmasını uygulayabilmemiz için bir graf yapımızın olması gerekiyor. Graf Oluşturma İşlemi nasıl gerçekleşir merak ediyorsanız lütfen ilgili yazımıza bakın.
 |
| gelişmiş graf yapısı |
BFS Algoritması C Kodu Nasıl Yazılır?
Her şeyden önce ana şablonu belirlememiz lazım. Bize neler lazım onları tespit etmemiz gerekiyor. Gereklilikleri sıralayalım.
Graf dizisi
Düğümlerin ziyaret edilip edilmeme durumunu saklayan değişken
Kuyruk Yapısı ve kontrolleri (boş mu dolu mu)
Bir önceki yazımızda text dosyasında oluşturulan grafın nasıl diziye aktarılacağını öğrendik. Text dosyasında istediğiniz değişikliği yaparak adjecency Matrix'inizi oluşturabilirsiz. İki düğüm arasında bağlantı varsa değerimiz 1'dir, yoksa 0'dır. Bu kadar basit. 5 düğümümüz varsa 5X5'lik bir matris oluşturulmalıdır. Bunu da unutmayın.
Şimdi ziyaret edilme durumlarını #define işlemiyle tanımlayabiliriz. Mesela
#define initial 1
#define waiting 2
#define visited 3
Biliyorsunuz BFS algoritmasında düğümlerin 3 ayrı durumu var. Henüz işlem yapılmayan düğüm initial pozisyondadır. Kuyruğa eklenen düğüm waiting durumuna geçer, kuyruktan çıkartılan düğüm ise visited olarak işaretlenir.
Kuyruk için kuyruğa eleman ekleme, kuyruktan eleman silme fonksiyonları gerekli. Burada ufak bir ayrıntı var, kuyruktan eleman silme fonksiyonumuz, bize bfs algoritması gereği, kuyruktan silinen elemanı geri döndürmeli. Yani biz silinen elemanı kaybetmemeliyiz. O işi de aşağıdaki gibi ek bir değişken oluşturarak halledebiliriz.
int kuyruksil()
{
int silinen_eleman;
if(front == -1 || front > rear)
{
printf("Kuyruk Bos!");
exit(1);
}
silinen_eleman = queueu[front];
front = front+1;
return silinen_eleman;
}
Gördüğünüz üzere silinen_eleman diye bir değişken oluşturdum. bu silinen elemanı, kuyruktan eleman silme işlemini yapmadan önce (front = front+1) silinen_eleman değişkenine aktardım, daha sonra return ile kullanıcıya geri döndürdüm. Fonksiyonun int tipinde bir fonksiyon olmasına dikkat edin, void değil.
Peki şimdi gelelim esas fonksiyona, bizim algoritmayı uygulamamız gerekiyor.
BFS Algoritması Fonksiyonu
void BFS(int v)
{
int i;
kuyruga_ekle(v);
state[v] = waiting;
while(!kuyruk_bos_mu())
{
v = kuyruktan_sil( );
printf("%d ",v);
state[v] = visited;
for(i=0; i<n; i++)
{
if(adj[v][i] == 1 && state[i] == initial)
{
kuyruga_ekle(i);
state[i] = waiting;
}
}
}
printf("\n");
}
Fonksiyonu satır satır anlatıyorum;
void BFS (int v) => int v başlangıç düğümüdür, istediğiniz değeri seçersiniz, ama unutmayın, düğüm 0'dan başlar. Mesela 5 düğümünüz varsa, düğümleriniz 0-4 arası numaralandırılır.
kuyruga_ekle(v) => baslangic düğümünü kuyruğa ekler
state[v] = waiting => state değişkeni düğümlerin durumunu hafıza tutan dizi değişkenidir. Biz kuyruğa eklenilen elemanı her zaman waiting durumuna getiririz.
while(!kuyruk_bos_mu()) => kuyruk dolu olduğu sürece dönecek while loop oluşturduk
v = kuyruktan_sil() => Yukarıda bahsetmiştim, kuyruktan sil fonksiyonumuz hem kuyruktan eleman siler, hem de silinen elemanı geri döndürür. Bu yüzden kuyruktan silinen eleman v değişkenine atanır.
printf("%d", v) => algoritma gereği kuyruktan silinen eleman outputumuzdur.
state[v] = visited => algoritma gereği kuyruktan silinen her eleman visited olarak işaretlenmelidir.
for(i=0; i<n; i++) => n sayısı burada düğüm sayımızdır, düğüm sayımız kadar döngümüz döner.
if(adj[v][i] == 1 && state[i] == initial) => bu satırda aranılan şart, iki düğümün arasında bağlantı bulunması ve state[i] değerinin hazır durumda olmasıdır. initial demek, henüz işlenmemiş demektir. Yani beklemede ya da ziyaret edilmiş pozisyona getirilmemiş düğüm anlamına gelir.
kuyruga_ekle(i) => döngümüz sürecinde i değerleri sürekli kuyruğa eklenir.
state[i] = Waiting => algoritmamızda her zaman kuyruğa eklenen veri waiting pozisyonuna getirilir.
BFS Algoritması Hazır C Kodu
Etiketler: bfs algoritması, graf oluşturma işlemi