7
Haz
C ile bfs algoritması
etiket algoritma bfs c Özgürlük İçin programlama
Enis T. YALÇINKAYA
Enis T. YALÇINKAYA

 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.


19
May
C ve dfs
etiket algoritma c dfs Özgürlük İçin programlama
Enis T. YALÇINKAYA
Enis T. YALÇINKAYA

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.


26
Kas
C ile bir diziyi sıralamak
etiket algoritma Özgürlük İçin programlama
Enis T. YALÇINKAYA
Enis T. YALÇINKAYA

Bir diziyi sıralamak için çeşitli yöntemler vardır. Bunlardan “Kabarcık Sıralama” (Bubble Sort) algoritmasını kullanarak bir dizinin nasıl sıralanabileceğini görelim:

#include<stdio.h>

void sirala(int *dizi,int u){
     int i,k,g;
     for(i=0;i<u;i++){
         for(k=i;k<u;k++){
             if(dizi[k]<dizi[i]){
                 g=dizi[k];           //yer değiştir
                 dizi[k]=dizi[i];
                 dizi[i]=g;
                 }
             }
     }
}

int main(){
    int k,dizi[10];
    printf(“Merhaba! 10 tane sayi girin ve biz de siralayalim :) \n”);
    for(k=0; k<10; k++){
        printf(“%d. sayiyi girin: “,k+1);
        scanf(” %d”,&dizi[k]);
}
    sirala(dizi,10);
    printf(“Dizinin sirali hali\n”);
    for(k=0; k<10; k++) printf(“%d\n”,dizi[k]);
    getch();
    return 0;
   
}

Kabarcık sıralama en basit ve en kötü algoritmalardan biridir. Eğer yujarıdaki örnekte 10 yerine 1000 sayı koysaydınız sıralama yaklaşık 5000 kat daha uzun sürecekti. Ama basit işlerde kullanabilirsiniz. Yaptığı şey dizinin her üyesini teker teker diğerleriyle karşılaştırmak ve eğer daha küçüğüyle karşılaşılırsa ikisinin yerini değiştirmek.