DFS Algoritması C Kodu Nasıl Yazılır


DFS Algoritmasının C kodunu yazmadan önce DFS Algoritması Çalışma Mantığı konusuna hakim olduğunuzdan emin olun.  Bunun da yanında, kodlama ortamında kullanacağınız graf dizisini text dosyasından alabilmelisiniz. Text dosyasından Graf okuma konusuna hakim olduğunuza da emin olmalısınız. Değilse algoritmayı hangi veri üzerinde uygulayacaksınız öyle değil mi :) ?

DFS Algoritması C kodu 2 şekilde yazılır.

Recursive DFS Algoritması
Iterative DFS Algoritması

Recursive DFS Algoritması

Yazılması çok kolaydır, çoğu kişi bu yöntemi tercih eder. Algoritma greedy bir algoritma olduğu için kendini çağırması sayesinde kolayca tüm düğümler gezilir. 

Recursive DFS Fonksiyonu

void DFS(int i)
{
    int j;
    printf("\n%d",i);
    visited[i]=1;
    
    for(j=0;j<n;j++)
       if(!visited[j]&&G[i][j]==1)
            DFS(j);
}

yukarıdaki fonksiyonu anlatmamız gerekirse, kendisine gönderilen başlangıç düğümünden başlıyor ve gönderilen düğümü visited olarak işaretliyor.

daha sonra döngüye giriyor, döngüdeki if şartı şu şekilde, ziyaret edilmemiş ve arada bağlantı olan düğümleri bulduğunda dfs(j) fonksiyonunu geri çağır. Peki işi hangi komut yapıyor? Esas numara visited[i] = i noktasında, bulunan her nokta visited olarak işaretleniyor, böylece traverse işlemi tamamlanıyor. Oldukça hoş bir yöntem, ancak ben iterativeciyim :) şimdi Iterative metodu anlatalım.

Iterative DFS Fonksiyonu

void DFS(int s)
{
    push(s);
state[s] = visited;

 while(!stack_bos_mu())
{
s = peek();
printf("%d", s);
pop();

 for(int i=0; i<n; i++)
{
if(!visited[i])
{
visited[i] = true;
push(i);
}
}
}
}

Iterative metotta mantık çok basit.

Kök düğüm yığına eklenir:  push(s)
Düğümün durumu visited yapılır: state[s] = visited
Daha Sonra Döngüye Girilir (döngü şartı yığının boş olmamasıdır)
Yığının tepesindeki eleman s değerine atanır: s = peek()
s değeri ekrana bastırılır
yığından eleman çıkartılır: pop()

daha sonra döngüye girilir;
eğer düğüm ziyaret edilmemişse
visited yapılır ve yığına eklenir.

Mutlaka Okuyun!
DFS Algoritması Hazır C Kodu

Etiketler: , , ,