Home / Algoritmalar / DFS Algoritması (Derin Öncelikli Arama) – Konu Anlatımı – C Kodu

DFS Algoritması (Derin Öncelikli Arama) – Konu Anlatımı – C Kodu

Bir önceki yazımızda Graflarda arama algoritmalarından Breadth First Search algoritmasını görmüştük. Bu yazımızda yine graflarda arama algoritmalarından olan DFS yani Depth First Search – Derin öncelikli Arama algoritmasını göreceğiz.

DFS Algoritması Nedir?

İçerik

BFS algoritmasıyla aynı amaca hizmet eden DFS Algoritması temelde graf yapısını (ya da ağaç veri yapısını) traverse etmeyi amaçlar. Ancak algoritması farklıdır. Hatırlarsanız BFS algoritması temelde en yakın komşuları ziyaret etmeyi hedeflemekteydi. DFS ise gidebildiği yere kadar gitmeyi, daha sonra geri dönerek grafı dolaşmayı hedefler. Yani BFS komşuları ziyaret etmeyi hedeflerken DFS ise sürekli olarak komşunun komşusuna gitmeyi amaçlamaktadır.

Algoritmadaki farklılık nedeniyle DFS algoritması kuyruk veri yapısı yerine Stack Veri Yapısı kullanmaktadır.

Stack Veri Yapısı ile ilgili yazılarımızı aşağıdaki Linklerimizden okuyabilirsiniz.

Stack Veri Yapısı Konu Anlatımı

DFS Algoritmasında ziyaret edilen düğümler yığına eklenir. Gidilecek komşu bulunamadığında pop ile yığından eleman atılır ve ziyaret edilebilecek komşu aranır. Aşağıda örnek üzerinde gösterelim.

DFS Algoritması Örnek

Eriştiğimiz herbir düğümü Stack Yapısına ekleyeceğiz, erişilecek düğüm kalmadığında stackten düğüm çıkartıp gidilebilecek düğüm var mı kontrol edeceğiz. Her ziyaret ettiğimiz düğümü ziyaret edildi olarak işaretlemeyi unutmayacağız.

1. Adım:

2 düğümünden başlıyoruz. (kafamıza göre seçtik)

Stack Durumu: top => 2

Ziyaret Edilen: 2

Output: 2

 

2. Adım:

3 düğümünü ekleriz. (0 düğümünü de ekleyebilirdik, fark etmez, herhangi bir komşuyu ekleyebiliriz)

Stack durumu: top => 3 => 2 (yani yığının tepesinde 3 var)

Ziyaret Edilen: 3

Output: 3

 

3. Adım:

4 düğümünü ekliyoruz. (1’i de ekleyebilirdik, herhangi komşudan bir tanesini seçiyoruz.)

Stack Durumu: top => 4=> 3 => 2

Ziyaret Edilen: 4

Output: 4

 

4. Adım:

5 düğümünü ekliyoruz.

Stack Durumu: top => 5 => 4 => 3 => 2

Ziyaret Edilen: 5

Output: 5

 

5. Adım:

Ziyaret Edilecek Düğüm kalmadı o halde stack’ten eleman sileriz. Çünkü ziyaret edilmemiş düğümleri Yığına Ekleyebiliriz.

Stack Durumu: top => 4 => 3 => 2 (5 çıktı)

not: Output edilecek düğüm bu adımda yok.

 

6. Adım:

4 düğümünün de Ziyaret Edilecek Düğümü kalmadı o halde stack’ten eleman sileriz (pop). Çünkü ancak ziyaret edilmemiş düğümleri Yığına Ekleyebiliriz.

Stack Durumu: top  => 3 => 2 (4 çıktı)

not: Output edilecek düğüm bu adımda yok.

 

7. Adım:

1 düğümünü ekliyoruz. Çünkü 3 düğümünün ziyaret edilmemiş komşusu bulunuyor.

Stack Durumu: top => 1 =3 => 2

Ziyaret Edilen: 1

Output: 1

 

8. Adım:

0 düğümünü ekliyoruz.

Stack Durumu: top => 0 => 1 =3 => 2

Ziyaret Edilen: 0

Output: 0

Adımlar burada bitmez, ama ziyaret edilecek düğüm kalmadığı için ben burada bitiriyorum.

Bundan sonraki adımların herbirinde Stack’ten eleman silinir, sonuç olarak 0 – 1 – 3 – 2 düğümleri stackten kaldırılır. Stack boşalınca algoritma durur. Yani yukarıdaki örnek için toplam 12 (8 + 4) adım gerçekleşir.

Algoritmamızın Çıktısı şu şekildedir.

2 – 3 – 4 – 5 – 1 – 0

DFS Algoritması C Kodu

Aşağıdaki kodu çalıştırabilmeniz için paylaştığım txt uzantılı dosyayı indirmeli, kodunuzun bulunduğu klasörle aynı klasöre yerleştirmelisiniz.

Matris.txt dosyasını indir


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

//Dizimizi tuttuğumuz array
int Array[6][6];
//ziyaret edilme durumlarını tuttuğumuz array
bool visited[6];

//recursice DFS kodu
void DFS(int root, bool visited[])
{
    int i;
    //başlangıç düğümünü ziyaret edildi olarak işaretliyoruz.
    visited[root] = true;
    printf("%d ", root);

    for( i = 0; i < 6; i++)
    {
    	//Eğer düğüm ziyaret edilmediyse her düğümün komşusunu 
    	//Yeni başlangıç noktasıymış gibi tekrar çağırıyoruz
    	//Çıktıları ise yukarıdaki print fonksiyonunda alıyoruz.
        if(Array[root][i] == 1 && visited[i] == false)
        {
            DFS(i, visited);
        }
    }
}

//matris dosyamızı okuyup diziye aktaran fonksiyon
void readMatrix()
{
    int i = 0;
    FILE *fp = fopen("matris.txt", "r");

    while(fscanf(fp, "%d %d %d %d %d %d",
                 &Array[i][0],
                 &Array[i][1],
                 &Array[i][2],
                 &Array[i][3],
                 &Array[i][4],
                 &Array[i][5]
                 ) != EOF)
    {
        i = i + 1 ;
    }
}


int main()
{

    readMatrix();
    DFS(3, visited);
    return 0;
}

Bir cevap yazın

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