C ile bfs algoritması

 Arama algoritmalarımıza yatay arama (bfs) ile devam ediyoruz.

Yatay arama derinlemesine aramadan farklı çalışır. Bir düğüme girdiğinde en uç noktaya varıncaya kadar gitmektense aynı dereceli diğer terimlere bakar. Bu işlemi nasıl yaptığını merak etmiştim. Meğerse kuyruk kullanılıyormuş. Kuyruk dediğimiz şey bir tür veri dizisi. Bu veri dizisine veriler en sona eklenir, veriler alınırken ilk baştaki veriden itibaren alınır. bfs algoritmasında her düğümün bağlı olduğu diğer düğümler kuyruğa eklenir ve kuyruktan alınan verilerde bfs tekrarlanır. Koda gelecek olursak:


//bfs.c 

#include <stdio.h>
int tablo[10][10];
int kuyruk[10];
int iz[10];
int aranan=6; //aranan düğüm
int bulundu=0;

// kuyruğa veri ekle
void ekle(int n)
{
    iz[n]=1;
    static int son=0;   //kuyruğun en sonu
    kuyruk[son]=n;
    son++;
    printf("%d Arama kuyruğuna eklendi!\n",n);
}

//kuyruktan veri al
int al()
{
    static int bas=0;   //kuyruğun en başı
    return kuyruk[bas++];
}

void bfs(int gel)
{
     printf("Giriliyor: %d\n",gel);
     int i;
     for(i=0;i<10;i++){
         if(!iz[i] && tablo[gel][i])
         {
             if(i==aranan)
             {
                 printf("Aranan %d bulundu!\n",i);
                 bulundu=1;
                 break;
             }
             else ekle(i);
         }
     }
}
int main()
{
    tablo[0][1]=tablo[1][0]=tablo[0][2]=tablo[2][0]=tablo[1][3]=tablo[3][1]=tablo[3][2]=tablo[2][3]=tablo[3][4]=tablo[4][3]=1;
    tablo[3][5]=tablo[5][3]=tablo[5][6]=tablo[6][5]=1;
    int i;
    while(!bulundu){
        iz[0]=1;
        bfs(al());

        }
     
    getch();
    return 0;
 
}


Programda her düğüme girerken neden “Giriliyor…” yazdırdığımı merak ediyorsanız, çok önemli bir sebebi yok. Sebebi hata korkusu. Ben de yeni başladığım için yanlış yazmış olabilirim. Bu şekilde hangi düğümlere girdiğini biliyorum ve programın doğru çalıştığından emin olabiliyorum.