Pengertian Algoritma BFS & DFS dan Contoh Program Menggunakan Algoritma BFS & DFS

Assalamu'alaikum warahmatullahi wabarakatuh

Nyatanya, masih ingin menulis. hehe :p

Kali ini saya mau berbagi tentang program C++ yang menggunakan Algoritma BFS & DFS.

Metode Pencarian BFS (breadth-first search) >> pencarian melebar pertama
Pada metode BFS, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1. Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya demikian pula dari kiri ke kanan hingga ditemukannya solusi.

Metode Pencarian DFS (depth-first search) >> pencarian mendalam pertama
Pada DFS, proses pencarian akan dilakukan pada semua anaknya sebelum dilakukan ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini diulangi terus hingga ditemukannya solusi.

Nah di bawah ini merupakan contoh coding programnya:

Berikut ini merupakan program pencarian matriks, dimana dari ketiga program tersebut menggunakan konsep algoritma bfs dan dfs

#include <stdio.h>

#include <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();

main(){

      int n,i,s,ch,j;

      clrscr();

      printf("masukkan angka ");

      scanf("%d",&n);

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

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

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

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

      printf("matriks adjasensi\n");

      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++)

      a:    vis[i]=0;

            printf("\nmenu");

            printf("\n1. bfs");

            printf("\n2. dfs");

            printf("\npilihan:");

            scanf("%d",&ch);

            printf("\nmasukan simpul sumber:");

            scanf("%d",&s);

      switch(ch){

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

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

            case 3: break;    }

      return(0);  }

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);   }

void add(int item){

      if (rear==19)

        printf("antrian full");

      else

        if (rear==-1){

        q[++rear]=item;

        front++;  }

      else

        q[++rear]=item; }

int del(){

      int k;

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

        return(0);

      else{

        k=q[front++];

        return(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);   }

void push(int item){

      if(top==19)

        printf("stack overflow");

      else

        stack[++top]=item;    }

int pop(){

      int k;

      if (top==-1)

        return(0);

      else{

        k=stack[top--];

        return(k);      }

}

Output dari program di atas adalah sebagai berikut:

Logika dari coding program di atas adalah sebagai berikut:

#include <conio.h>

peryataan conio.h. adalah library pada C yang digunakan untuk mengkoneksikan pernyataan clrscr() dengan program yang kita buat. Tanpa menggunakan library ini, kita tidak bisa menggunakan fungsi prototype seperti: gotoxy(), clrscr(), clreol().

#include <stdio.h>

Pernyataan di atas digunakan sebagai standard library yang berfungsi untuk I/O  package maksudnya digunakan jika kita ingin pada program kita menggunakan fungsi standard input atau output bisa dikatakan seperti portable input/output package. Tanpa menggunakan library ini, kita tidak bisa menggunakan perintah-perintah input/output pada program kita.

void add(int item);
void bfs(int s, int n);
void dfs(int s, int n);
void push(int item);

Pernyataan di atas digunakan untuk mendefinisikan procedure untuk, antrian penuh (void add), perhitungan bfs (void bfs), perhitungan dfs (void dfs) dan jika terjadi kelebihan data (void push).

main() {

Pernyataan di atas adalah main procedure (prosedur utama dalam program ini). Fungsinya sama seperti public.static.void.main(String args[]) { pada bahasa pemrograman java.

clrscr();

Pernyataan di atas digunakan untuk membersihkan layar ketika program dieksekusi.

int n,i,s,ch,j;

Pernyataan diatas digunakan untuk mendeklarasikan variable n, i, s, ch dan j yang bertipe data integer (bilangan bulat).

printf("matriks adjasensi\n ");

Pernyataan printf di atas digunakan untuk mencetak tulisan yang ada diantara tanda kutip “ ”, yaitu Algoritma Brute Force. Pernyataan \n digunakan agar tulisan utama yang dicetak ada jedanya (enter) pada saat program dieksekusi.

scanf("%d",&n);

Pernyataan scanf digunakan untuk menyimpan angka yang kita input ketika program dieksekusi. Disini terdapat %d yang mengartikan data inputan akan ditampilkan dalam bentuk decimal, dan &x mengartikan data inputan akan disimpan sementara pada variable n.

a :

Pernyataan di atas digunakan sebagai identitas blok pernyataan yang nantinya akan dipanggil oleh program ketika program dieksekusi. 

switch(ch){

Pernyataan di atas digunakan sebagai kondisi percabangan dalam program ini, dimana pilihannya terdapat pada case-case yang dideklarasikan setelah pernyataan ini.

case 1:bfs(s,n);

Pernyataan di atas digunakan sebagai pilihan pertama dari percabangan dalam program ini, dimana program akan mengeksekusi blok procedure bfs.

case 2:dfs(s,n);

Pernyataan di atas digunakan sebagai pilihan kedua dari percabangan dalam program ini, dimana program akan mengeksekusi blok procedure dfs.

goto a;

Pernyataan di atas digunakan untuk mengarahkan program agar melanjutkan eksekusi ke blok program a:

case 3: break; }

Pernyataan di atas digunakan sebagai pilihan ketiga jika angka yang kita masukkan bukan 1 atau 2, maka program akan berhenti mengeksekusi (break).

return(0); }

Pernyataan di atas digunakan untuk mengambil data masukkan untuk melanjutkan eksekusi ke baris program berikutnya.

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

Pernyataan for di atas digunakan sebagai kondisi perulangan dengan ketentuan program akan mengeksekusi dimulai dari bilangan 1, program akan berhenti mengeksekusi jika variable i telah lebih besar daripada variable n, dan variable i akan bertambah satu setiap terjadi perulangan.

if(p!=0)

Pernyataan if di atas digunakan sebagai kondisi percabangan jika hasil bagi variable p tidak sama dengan 0.

getch();

berguna unutk membaca sebuah karakter, bisa juga membaca tombol, getch() tidak akan menampilkan karakter dari tombol yang ditekan. Sebuah getch() bisa pula digunakan untuk menunggu sembarang tombol ditekan. Pada keadaan seperti ini, hasil dari fungsi ini tidak perlu diletakkan ke variable, atau dipascal dapat diartikan sebagai readln

Disini saya membuat programnya menggunakan TurboC++, untuk melihat hasil dari program yang kita buat terlebih dahulu kita harus menyimpan (save as) dengan format .c atau .cpp, jika telah kita simpan selanjutnya adalah mengkompile dengan langkah: Project > Compile atau bisa menekan Alt+F9, dan untuk melihat outputnya: Debug > Run atau bisa menekan Ctrl+F9. 

Sekian yang dapat saya bagian mengenai Algoritma BFS & DFS dan contoh programnya. Semoga bermanfaat bagi yang membacanya. Akhir kata, terima kasih dan ...

Wassalamu'alaikum warahmatullahi wabarakatuh