Home / Algoritmalar / BFS Algoritması (Geniş Öncelikli Arama) – Konu Anlatımı – C Kodu

BFS Algoritması (Geniş Öncelikli Arama) – Konu Anlatımı – C Kodu

Breadth First Search (BFS) algoritması Türkçe olarak geniş öncelikli arama şeklinde ifade edilir. Algoritma mantığını anlamadan önce bu algoritmanın amacı nedir onu bilmemiz gerekir. BFS Graflarda arama algoritmasıdır. Arama kısmına takılmayın, temelde traverse yani dolaşma işlemini yapar. Dolaşma (Traverse) yaparken handle ederek istediğiniz veriyi bulabilmenize olanak sağlar.

BFS Algoritması Graf ve Ağaç veri yapıları üzerinde uygulanır. Düğümleri dolaşır. Her düğüme bir kez varmayı hedefler. Tüm düğümler arasında ilişki bulunuyorsa, tüm düğümleri dolaşmanıza olanak sağlar. Graflar veri yapısı olarak Adjacency Matrix adı verilen komşuluk matrislerinde tutulabilir. Bu kolay bir yöntemdir. İki boyutlu bir dizi oluşturarak düğümler arasındaki ilişkiyi gösterebilmeniz mümkündür.

BFS Algoritması Nedir?

BFS Algoritması temel prensip olarak en yakın düğümleri ziyaret etmeyi hedefler. En yakındaki düğümler taranarak uzaktaki düğümlere gidilir. Yakın olan düğümler öncelikli olarak ziyaret edileceği için bizim bir veri yapısı kullanmamızı gerektirmektedir. BFS Algoritmasında Kuyruk Veri Yapısı Kullanılır.

Ziyaret edilen düğümün komşuları kuyruğa atılır. Her adımda kuyruktan bir eleman çıkartılır ve bu mantıkla ziyaret edilmemiş düğümler kuyruğa eklenir. Bu şekilde tüm düğümler dolaşılır. Eğer bir düğümü arıyorsanız sadece bir if satementı ile işinizi halledebilirsiniz. Tabii ki bu algoritmayı adım adım örnekle anlatacağız.

BFS Algoritması Örneği

örnek yapı

Yukarıdaki örneği kullanalım (internetten buldum) Başlangıç düğümü olarak “2” düğümünü kullanacağız. Şimdi Adım adım nasıl yapacağımıza göz atalım.

 

1. Adım:

2 düğümü kuyruğa eklenir.

Ziyaret Edilen Düğümler: 2

Kuyruk Durumu: 2

Kuyruktan Çıkan: Yok

Output (Çıktı) : 2

 

2. Adım:

0 ve 3 düğümü kuyruğa eklenir.

Ziyaret Edilen Düğümler: 2 – 0 – 3

Kuyruk Durumu: 03

Kuyruktan Çıkan: 2

Output (Çıktı) : 2 – 0 – 3

 

3. Adım:

1 düğümü kuyruğa eklenir. (Neden? – çünkü kuyruk durumuna bakın, kuyruğun en başında 0 var, bu yüzden 0’ın ziyaret edilmemiş komşusu olan 1 eklenir)

Ziyaret Edilen Düğümler: 2 – 0 – 3

Kuyruk Durumu: 31

Kuyruktan Çıkan: 0

Output (Çıktı) : 2 – 0 – 3 – 1

HATIRLATMA! Her adımda kuyruktan eleman çıkartılır

 

4. Adım:

1 düğümü kuyruğa eklenir. (Neden? – çünkü kuyruk durumuna bakın, kuyruğun en başında 0 var, bu yüzden 0’ın ziyaret edilmemiş komşusu olan 1 eklenir)

Ziyaret Edilen Düğümler: 2 – 0 – 3

Kuyruk Durumu: 31

Kuyruktan Çıkan: 0

Output (Çıktı) : 2 – 0 – 3 – 1

 

5. Adım:

4 düğümü kuyruğa eklenir. (Neden? – çünkü kuyruk durumuna bakın, kuyruğun en başında 3 var, bu yüzden 3’ün ziyaret edilmemiş komşusu olan 4 eklenir)

Ziyaret Edilen Düğümler: 2 – 0 – 3 – 4

Kuyruk Durumu: 14

Kuyruktan Çıkan: 3

Output (Çıktı) : 2 – 0 – 3 – 1 – 4

 

6. Adım:

Bu adımda kuyruğa eleman eklenmez (Neden? – çünkü kuyruk durumuna bakın, kuyruğun en başında 1 var, 1 düğümünün ziyaret edilmemiş komşusu yok.)

Ziyaret Edilen Düğümler: 2 – 0 – 3 – 4

Kuyruk Durumu: 4

Kuyruktan Çıkan: 1

Output (Çıktı) : 2 – 0 – 3 – 1 – 4

 

7. Adım:

Bu adımda 5 düğümü kuyruğa eklenir (Neden? – çünkü kuyruk durumuna bakın, kuyruğun en başında 4 var, 4 düğümünün ziyaret edilmemiş tek komşusu 5 düğümüdür.)

Ziyaret Edilen Düğümler: 2 – 0 – 3 – 4 – 5

Kuyruk Durumu: 5

Kuyruktan Çıkan: 4

Output (Çıktı) : 2 – 0 – 3 – 1 – 4 – 5

 

8. Adım:

Bu adımda hiçbir işlem yapılmaz. Çünkü kuyruk boş ve eklenebilecek ziyaret edilmemiş düğüm yoktur. Bu yüzden algoritma burada sonlanır.

Algoritmanın Çıktısı Şu şekildedir. :

2 – 0 – 3 – 1 – 4 – 5

BFS Algoritması C Kodu

Kodu direkt bilgisayarınıza kopyalayıp çalıştırmadan önce aşağıdaki komşuluk matrisini içeren “matris.txt” isimli dosyayı indirin. Bu dosyanın kodlarınızın bulunduğu klasörde olmasına dikkat edin.

Matris Text Dosyasını İndir

 


#include <stdio.h>
#include <stdbool.h>

// author Muhammed Eminoğlu
// twitter => @algoritmauzmani

//Graf veri yapımızı 2 boyutlu dizide tutacağız
int graph[6][6];
//Düğümlerin ziyaret edilip edilmediğini tutacağımız değişken.
bool visited[5];

//Kuyruk veri yapımı bağlı listede tutacağım için struct node oluşturdum.
struct node{
    int data;
    struct node *next;
};

//Kuyruğun en ön ve en arka elemanları için düğüm oluşturdum.
struct node* first = NULL;
struct node* last = NULL;

//Düğüm oluşturan fonksiyon
struct node* createNode(int x)
{
    struct node* newNode = (struct node*)malloc(sizeof(struct node));
    newNode->data = x;
    newNode->next = NULL;
    return newNode;
}

//kuyruğa eleman ekleyen fonksiyon
void enQueue(int x)
{
    struct node* newyNode = createNode(x);
    if(first == NULL)
    {
        first = newyNode;
        last = newyNode;
    }
    else
    {
        last->next = newyNode;
        last = newyNode;
    }
}

//kuyruktan eleman çıkaran fonksiyon
void deQueue()
{
    if(first == NULL)
    {
        printf("\n Your Queue is already empty please enqueue an item");
        return;
    }

    if(first->next == NULL)
    {
        first = NULL;
        last = NULL;
    }
    else
    {
        struct node* secondNode = first->next;
        free(first);
        first = secondNode;
    }

}

//kuyruk boş mu diye kontrol eden fonksiyon
bool isEmpty()
{
    if(first == NULL)
        return true;
    else
        return false;
}

//kuyruğun en önündeki elemanı return eden fonksiyon
int next()
{
    return first->data;
}

//Temel algoritmamız burada. Her şey buna hazırlıktı.
void BFS(int root)
{
    int i;
    //Tüm düğümleri ilk başta ziyaret edilmemiş olarak set ettik.
    for(i = 0; i < 6; i++)
    {
        visited[i] = false;
    }

    //Başlangıç düğümünü ziyaret edildi olarak işaretledik ve kuyruğa ekledik.
    visited[root]  = true;
    enQueue(root);

    //Döngümüzün temel şartı kuyruğun boş OLMAMASI!
    while(isEmpty() == false)
    {
    	//döngünün her adımında root değerine kuyruğun en önündeki elemanı atayıp çıktı veriyoruz.
        root = next();
        printf("%d ", root);
        //Sitedeki (www.algoritmauzmani.com) yazıda da belirttiğim gibi her adımda kuyruktan eleman çıkarıyoruz
        deQueue();

        //Bu döngü bir düğümün ziyaret edilmemiş komşularını kuyruğa ekliyor.
        //Burası çok önemli if satırına dikkat edin.
        for( i = 0; i < 6; i++)
        {
        	//Eğer bir düğüm ziyaret edilmemişse ve aralarında bağlantı var ise...
            if(visited[i] == false && graph[root][i] == 1)
            {
                visited[i] = true;
                enQueue(i);
            }
        }
    }
}

//Text dosyasına girdiğimiz komşuluk matrisini okuyup dizimize aktaran fonksiyon.
void readGraph()
{
    int i = 0;
    FILE *fp = fopen("matris.txt", "r");
    while(fscanf(fp, "%d %d %d %d %d %d",
                 &graph[i][0],
                 &graph[i][1],
                 &graph[i][2],
                 &graph[i][3],
                 &graph[i][4],
                 &graph[i][5]) !=EOF){
        i = i + 1;
    }

}

int main()
{
    readGraph();
    BFS(2);
    return 0;
}

3 comments

  1. Hocam txt dosyası şeklinde matrisi aynı klasöre koydum fakat kodu compile yaptığımda 25. satirrda hata alıyorum [Error] ‘malloc’ was not declared in this scope

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir