Algoritma DFS dan BFS dengan Bahasa C

Hallo Bloggers, masih melanjutkan materi bahasa C dan kali ini penggunaan bahasa C dalam membentuk algoritma DFS (Depth First Search) dan BFS (Breadth First Search).
Untuk pengertian kedua Algoritma tersebut, teman-teman dapat mencarinya pada referensi-referensi yang ada di internet.

Berikut ini listing programnya.

Kemudian berikut ini adalah penjelasannya.

#include <stdio.h>

#include <conio.h>

      Saat program dijalankan akan dieksekusi peanggilan header yang berfungsi untuk menggunakan header stdio.h dan conio.h

int q[20],top = -1,front = -1, rear = -1, a[20][20], vis[20], stack[20];

int del();

void add(int item);

void bfs(int s, int n);

void dfs(int s, int n);

void push(int item);

int pop();

      Pendeklarasian dari program utama terdiri dari variabel-variabel dengan tipe datanya kemudian dengan fungsi-fungsi yang akan digunakan.

main(){

      int n,i,s,ch,j;

      clrscr();

      printf("masukkan angka yang di inginkan ");

      scanf("%d",&n);

      for(i=1;i<=n;i++){

             for(j=1;j<=n;j++){

      printf("masukkan %d jika mempunyai nilai simpul %d selain itu 0",i,j);

      scanf("%d",&a[i][j]);  

}

}

      Penggalan program diatas mendeklarasikan fungsi utama pada program tersebut. Yang akan ditampilkan permintaan “masukkan angka yang diinginkan”. Kemudian ditampilkan serta diminta memasukan input sebanyak (n x n), sesuai dengan input sebelumnya dan akan membentuk seperti matriks.

 for(i=1;i<=n;i++){

      for(j=1;j<=n;j++){

      printf("%d ",a[i][j]);  }

      printf("\n");     }

      for(i=1;i<=n;i++)

      Selanjutnya menjalankan perulangan bersarang. Pada proses ini berguna untuk mengeluarkan semua nilai yang ada dalam matriks.

a:    vis[i]=0;

            printf("\nmenu");

            printf("\n1. bfs");

            printf("\n2. dfs");

            printf("\npilihan:");

            scanf("%d",&ch);

            printf("\nmasukan simpul sumbernya:");

            scanf("%d",&s);

      switch(ch){

            case 1:bfs(s,n); goto a;

            case 2:dfs(s,n); goto a;

            case 3: break;    }

      return(0);  }

      Penggalan program diatas akan menampilkan menu yang ada pada program ini, pilihan pertama bfs selanjutnya dfs. Setelah itu diminta memasukan pilihannya. Input dari user tadi akan memasuki percabangan dengan switch. Jika memilih 1 akan dijalankan fungsi bfs, jika memilih 3 akan menjalankan fungsi dfs. Keduanya memerlukan parameter variabel s dan n.

void bfs(int s,int n){

      int p,i;    add(s);     vis[s]=1;   p=del();

      if(p!=0)

      printf("%d ",p);

      while(p!=0){

            for(i=1;i<=n;i++)

            if((a[p][i]!=0)&&(vis[i]==0)){

                  add(i);     vis[i]=1;   }

            p=del();

            if(p!=0)

            printf("%d ",p);  }

      for(i=1;i<=n;i++)

      if (vis[i]==0)

      bfs(i,n);   }

     

Alur dari fungsi bfs adalah untuk mencari solusi dari level hierarkhi yang sama ke level berikutnya secara melebar, terdapat beberapa variabel yaitu p, i, add, vis, dan p, dan memiliki percabangan inti, jika a dari variabel array p dan i tidak sama dengan 0 maka variabe vis indeks i = 0, lalu proses selanjutnya akan menambah nilai pada variabel add, hingga selesai.

void add(int item){

      if (rear==19)

        printf("antrian penuh");

      else

        if (rear==-1){

        q[++rear]=item;

        front++;  }

      else

        q[++rear]=item; }

      Alur fungsi add dengan nilai jika nilai rear = 19 maka akan dicetak antrian penuh, jika tidak maka variabel q = item nilai front bertambah 1, jika tidak nilai q = item saja.

 int del(){

      int k;

      if((front>rear)||(front==-1))

        return(0);

      else{

        k=q[front++];

        return(k);      }}

      Alur fungsi del adalah untuk deklarasi sub program del dengan tipe data integer, yang didalam terdapat percabangan membandingkan antara nilai front dengan rear, jika nilai front lebih besar atau front = -1 maka program akan kembalikan nilai menjadi 0, jika tidak nilai k = q dengan kembalinya nilai variabel k.

void dfs(int s, int n){

      int i,k;    push(s);    vis[s]=1;   k=pop();

      if(k!=0)

        printf("%d ",k);

      while(k!=0){

        for(i=1;i<=n;i++)

        if((a[k][i]!=0)&&(vis[i]==0)){

          push(i);      vis[i]=1;   }

        k=pop();

        if (k!=0)

          printf("%d ",k);    }

      for(i=1;i<=n;i++)

      if (vis[i]==0)

            dfs(i,n);   }

      Alur fungsi dfs adalah sub program untuk DFS dengan konsep bahwa solusi yang dicari terlebih dahulu adalah level yang paling bawah kemudian naik ke hierarki sebelahnya hingga ketemu solusi, yang membedakan antara bfs adalah adanya variabel pop pada dfs.

           

 void push(int item){

      if(top==19)

        printf("stack overflow");

      else

        stack[++top]=item;    }

      Alur fungsi push diatas adalah sub program push dengan item bertipe integer mempunyai percabangan yang mengatakan bahwa jika nilai pada top = 19 maka program akan mencetak nilai stack overflow jika tidak maka nilai stack akan sama dengan item.

int pop(){

      int k;

      if (top==-1)

        return(0);

      else{

        k=stack[top--];

        return(k);      }

      Alur fungsi pop diatas adalah sub program pop dengan percabangan jika nilai top = -1 maka nilai akan kembali ke 0 dan kembali ke program utama jika tidak maka nilai k pada stack top berkurang 1 dan akan kembali ke variabel k.

Sekarang saatnya untuk menjalankan program ini dan berikut adalah tampilan outputnya.