C ve dfs

Bu aralar python yerine C’ye çalışmayı düşündüm. Sonra Halil’e “Bana C öğretsene, Python çok yavaş” dedim tabii o da kabul etti. İlk olarak bazı algoritmaları öğretti. Bunlar arama algoritmaları. Ben de ilk olarak dfs’i yazdım.

Dfs’in ne olduğuna gelince: “Derinlemesine arama” demek oluyor. Yani düğümlerden birine girdiğinizde aramaya ona bağlı düğümlerden devam ediyorsunuz. Eğer düğümler çıkmaza girerse o zaman geri dönüp hemen yanındaki düğüme geçiyorsunuz. Kod şöyle:

#include<stdio.h>

int tablo[1000][1000];
int n=7;
int aranan=6;
int iz[1000];

void dfs(int gel){
    int i;
    iz[gel]=1;
    for(i=0;i<n;i++)
    {
        if(!iz[i] && tablo[gel][i])
        {
            printf("Giriliyor: %d \n",i);
            if(i==aranan)
            {
                printf("Aranan %d Bulundu\n",i);
                break;
            }
            else dfs(i);
        }
    }
    printf("Çıkılıyor: %d\n",gel);
}

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;
    dfs(0);
    printf("Arayan Bulur!\n");
    return 0;
}

Düğümleri oluştururken bir tablo oluşturup eğer düğümler arasında bağ varsa tablonun o sayıların kesişimine gelen elemanını (yani eğer 4, 2′ye bağlıysa tablo[4][2]=tablo[2][4]=1) 1 yapıyorsunuz. Tablo simetrik olmalı, çünkü mesela 4 2′ye bağlıysa 2 de 4′e bağlıdır. Bu değerleri bir girdi dosyasından da okuyabilirsiniz ama ben basit olması için programda elle girmiş oldum. Bunu yazdıktan sonra Halil “Bir de şey yaz sen: iki düğüm alsın kullanıcıdan, birinden diğerine gidilip gidilemeyeceğini göstersin.” Ama ben uğraşmadım. Bu algoritmadan sonra da bfs yazmaya çalışacağım. Yazdığım zaman onu da buraya korum. Hepinize iyi günler.