Laporan Akhir Perancangan dan Analisis Algoritma

Laporan Akhir Pertemuan ke-4 BFS dan DFS

LISTING PROGRAM

#include <stdio.h>

#include <conio.h>

#include <windows.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;

      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("\nMatriks 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("\n3. Keluar");

            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:

            DestroyWindow(GetActiveWindow());

return 0;

            }

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

}

LOGIKA PEMROGRAMAN

Algoritma yang di gunakan pada listing program di atas adalah BFS dan DFS.

·         BFS (Breadth First Search) adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpul-simpul yang tadi dikunjungi, demikian seterusnya.

·         DFS (Depth First Search) adalah algoritma yang melakukan pencarian secara menelusuri semua akar-akarnya. Jika apa yang dicari tidak ada pada akar tersebut, pencarian akan pindah ke node lain pada level yang sama, pencariannya hampir sama dengan BFS yaitu dimulai dari nilai terkecil atau yang paling dekat.

#include <stdio.h>

Source code yang digunakan untuk Standar input-output pada bahasa pemrograman ini. Tanpa file library ini maka perintah-perintah yang ada di dalam file tersebut tidak akan bisa dieksekusi saat sebuh program di jalankan.

#include <conio.h>

Untuk header di atas digunakan bila melibatkan clrscr( ), yaitu perintah untuk membersihkan layar dan fungsi getch( ) untuk menerima sembarang input keyboard dari user.

#include <windows.h>

Dan header di atas digunakan untuk mengontrol window yang digunakan, contohnya seperti menutup window yang sedang aktif.

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

Variabel dengan tipe data yang sama yaitu integer. Variabel q, vis, dan stack memiliki index 1 dimensi dengan jumlah index 20, sedangkan variabel a memiliki index 2 dimensi dengan jumlah masing masing index 20. Dan variabel top, front dan rear sudah di beri nilai awal -1.

int del();

void add(int item);

void bfs(int s, int n);

void dfs(int s, int n);

void push(int item);

int pop();

Fungsi int del dan pop akan mengembalikan nilai saat proses dilakukan pada blok programnya. Kemudian keempat fungsi void masing masing memiliki parameter, fungsi void dan push memiliki parameter in item, sedangkan void bfs dan dfs memiliki parameter int s dan int n.

main(){

Fungsi utama yang wajib ada agar program dapat berjalan.

printf("Masukkan Angka : ");

Perintah yang digunakan berfungsi untuk menampilkan tulisan pada layar.

scanf("%d",&n);

Perintah yang digunakan berfungsi untuk menyimpain nilai sementara pada variabel n dan berbentuk desimal.

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

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

Perulangan dalam perulangan menggunakan “for” dimana nilai i sama dengan 1 jika nilai i lebih kecil atau sama dengan nilai n maka nilai i akan bertambah. Kemudian dimana nilai j sama dengan 1 jika nilai j lebih kecil atau sama dengan nilai n maka nilai j akan bertambah dan akan kembali ke perulangan variabel i.

switch(ch){

  case 1:bfs(s,n);

  goto a ;

  case 2:dfs(s,n);

  goto a ;

  case 3:DestroyWindow(GetActiveWindow());

  return 0;}

return(0);}

Percabangan menggunakan “switch case” dimana jika kita menginput data yang bernilai 1 maka akan memanggil fungsi bfs dengan variabel s dan n, kemudian program akan melanjutkan ke label a. Jika yang kita input bernilai 2 maka akan memanggil fungsi dfs dengan variabel s dan n, kemudian program akan melanjutkan ke label a. Dan jika inputan bernilai 3 maka window akan tertutup. Lalu akan mengembalikan nilai default ke nol.

add(s);

vis[s]=1;

p=del();

Memanggil fungsi add dengan memberikan parameter s, kemudian vis dengan index s bernilai 1 dan variabel p bernilai fungsi del.

while(p!=0){

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

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

add(i);

vis[i]=1;}

Perulangan menggunakan “while” dimana jika nilai p tidak sama dengan 0 akan melalukan perulangan “for” dimana nilai i sama dengan 1 jika nilai I lebih kecil atau sama dengan nilai n maka nilai i akan bertambah. Kemudia akan memeriksa kondisi dengan percabangan “if” dimana jika nilai a dengan index p dan i tidak sama dengan 0 dan nilai vis dengan index i tidak sama dengan 0 maka proses akan berlanjut ke tahap selanjutnya.

void add(int item){

  if (rear==19)

    printf("Antrian full");

  else

    if (rear==-1){

      q[++rear]=item;

      front++;}

    else

      q[++rear]=item;}

Memanggil fungsi add dan melakukan percabangan didalam percabangan menggunakan “if else” dimana jika nilai rear sama dengan 19 maka akan mencetak tulisan pada layar. Dan jika nilai rear tidak sama dengan 19 akan melakukan percabangan lagi dimana jika nilai rear sama dengan -1 maka akan memberikan nilai q dengan index nilai rear bertambah satu sama dengan item dan nilai variabel front akan bertambah satu. Dan jika nilai rear tidak sama dengan -1 akan memberikan nilai q dengan index nilai rear bertambah satu sama dengan item.