C Programlama BFS Algoritması (Breadth-First Search)

BFS (Breadth First Search) Nedir?

İsminin Türkçe’ye çevirmek istersek Genişlik Öncelikli Arama diyebiliriz. Bilmiyorum dikkatinizi çekti mi iki algoritmanın de son 2 kelimesi aynı “First Search” yani öncelikli arama anlamına geliyor. Algoritmanın amacı, bir graph’ı gezmek.Önceliği farklılıkları da graph gezme algoritmalarını oluşturuyor.

BFS Nasıl Çalışır?

Önceliğimiz derinlik değil de genişlik olacak. Yani her bir node için aynı anda bütün müsait çocuklarına gideceğiz ve oradaki gezme işlemimiz bittiğinde aynı şekilde bu sefer gezdiğimiz node’ların çocuklarına aynı anda gideceğiz. İkidir “aynı anda” ifadesini kullanıyorum ancak malesef gerçek anlamda aynı anda gidemeyeceğiz. Çünkü algoritmanın lineer bir şekilde ilerlemesini istiyoruz. Bunu sağlamak için ise queue adında bir veri yapısı kullanacağız. Bu veri tipini basit biri dizi olarak düşünebilirsiniz ancak dizinin sadece o an en üstte bulunan elemanını silebiliyoruz ve diziye sadece en aşağıdan veri ekleyebiliyoruz. Daha fazla ayrıntıya veri yapıları dersinde değinmenin daha uygun olacağını düşünüyorum.

Öncelikle başlangıç noktasını queue’ya ilk veri olarak ekliyoruz. Daha sonra queue dizisi boş olmadığı sürece aşağıdaki işlemleri yapıyoruz.

1. Eğer queue boş ise programı bitir. Değil ise queue’nun en üstündeki node’u al.
2. Bu node’un bütün çocuklarını döngü yardımıyla gez.
3. Daha önce gezilmemiş bütün çocuklarını queue’nun altına ekle.
4. Şu anki node’u gezme işlemi bittiği için queue’dan sil.
5. 1. Adıma geri dön.

BFS Örneği

İlk olarak B’yi queue’ya ekleyelim. B’nin gezilmesi müsait çocuklarını queue’ya ekliyoruz bunlar A ve C. B’yi gezme işlemimiz bittiği için queue’dan siliyoruz. Önce A’yı eklediğimiz için sıra A’ya geliyor. A’nın gezilebilir çocukları D ve E bunları da ekleyip A’yı siliyoruz. Şu an queue’nun içindeki sıralama C D E şeklinde. C’yi alıyoruz ve F’yi ekliyoruz. Daha sonra sırayla D, E ve F’yi geziyoruz. En son F’yi de gezdikten sonra siliyoruz ve queue’da veri kalmıyor. Bu nedenle program bitiyor ve bütün node’ları yollara uygun bir biçimde gezmiş oluyoruz.

BFS Karmaşıklığı

DFS’e benzer bir şekilde her bir node’a yalnızca 1 defa gittiğimiz için karmaşıklık O(N) oluyor.

C Programlama Örneği

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;
void bfs(int v)
{
 for(i=1;i<=n;i++)
  if(a[v][i] && !visited[i])
   q[++r]=i;
 if(f<=r)
 {
  visited[q[f]]=1;
  bfs(q[f++]);
 }
}
int main()
{
 int v;
 system("CLS");
 printf("\n Enter the number of vertices:");
 scanf("%d",&n);
 for(i=1;i<=n;i++)
 {
  q[i]=0;
  visited[i]=0;
 }
 printf("\n Enter graph data in matrix form:\n");
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
   scanf("%d",&a[i][j]);
 printf("\n Enter the starting vertex:");
 scanf("%d",&v);
 bfs(v);
 printf("\n The node which are reachable are:\n");
 for(i=1;i<=n;i++)
  if(visited[i])
   printf("%d\t",i);
  else
   printf("\n Bfs is not possible");
 getch();
}