Friday, February 26, 2016
Pada
tutorial ini akan dibahas mengenai BFS dan DFS, dimana BFS sendiri merupakan
metode pencatian secara melebar yang mengunjungi simpul secara preorder yaitu
mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga
dengan simpul tersebut terlebih dahulu, DFS merupakan metode pencarian yang
dilakukan pada satu node dalam setiap level dari yang palng kiri.
Tutorial ini menggunakan kasus mencari matriks adjasensi, bfs dan dfs
menggunakan C++. Untuk memulainya, lakukan langkah-langkah berikut :
1. Jika belum
memiliki compiler c++ nya, maka harus mendownload terlebih dahulu ( disini saya
menggunakan dev c++ ).
2. Jika sudah
ketikkan listing program berikut :
LISTING PROGRAM
#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("matrik
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("\nMasukkan
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);
}}
|
LOGIKA PROGRAM
Apabila
sudah mengetikkan programnya, disimpan dengan nama matriks.cpp
#include
<stdio.h> merupakan Library untuk input/output pada
program,tanpa
menyertakan code ini kita tidak bisa melakukan pengoperasian input dan output
#include<conio.h> merupakan fungsi library
console i/o untuk memanggil fungsi input output untuk menggunakan perintah
getch
§ int q[20],top=-1,front=-1,rear=-1,a[20][20],vis[20],stack[20];
int del();
Digunakan untuk :
mendeklarasikan nilai
q yang panjangnya 20, top, front, rear = -1 yang bertipe integer.
§ void add(int item);
Digunakan untuk :
mendefinisikan
prosedur antrian penuh.
§ void bfs(int s, int n);
void dfs(int s, int
n);
Digunakan untuk :
Melakukan perhitungan
secara bfs dan perhitungan dfs.
§
void
push(int item);
Digunakan untuk :
listing diatas digunakan
jika terjadi kelebihan data.
§
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]);
Digunakan untuk :
fungsi utama yang
digunakan dalam program ini, variable n,I,s,ch,j dideklarasikan dengan bertipe
data integer, dan fungsi ini digunakan untuk memasukkan inputan jumlah
simpulnya, serta akan melalukan perintah perulangan, lalu mencentak teks dan
untuk meminta memasukkan nilai simpulnya.
§
for(i=1;i<=n;i++){
printf("Matriks
adjasensi\n");
for(j=1;j<=n;j++){
printf("%d",a[i][j]);
}
printf("\n");
Digunakan untuk :
menampilkan matriks adjasensi
dari inputan simpul yang sudah dimasukkan sebelumnya, dan akan melakukan
perulangan jika nilai j=1 dan j lebih
kecil sama dengan n dan nilai j bertambah 1, akan menampilkan matriksnya.
§ for(i=1;i<=n;i++)
a:
vis[i]=0;
printf("\nmenu");
printf("\n1. Bfs");
printf("\n2. Dfs");
printf("\nPilihan : ");
scanf("%d",&ch);
printf("\nMasukkan simpul sumber : ");
scanf("%d",&s);
Digunakan untuk :
Menampilkan teks
“menu”,”1.Bfs”,”2.Dfs”,”Pilihan:”,dan ”Masukkan simpul sumber:”
§
printf("matriks adjasensi\n ");
Digunakan untuk :
Mencetak tulisan matriks
adjasensi. Pernyataan \n digunakan agar tulisan utama yang dicetak ada jedanya
(enter) pada saat program dieksekusi.
§
scanf("%d",
&s);
Digunakan untuk :
Menyimpan angka yang kita
input ketika program dieksekusi. Disini terdapat %d yang mengartikan data
inputan akan ditampilkan dalam bentuk decimal.
§
For(i=1;i<=n;1++){
Digunakan untuk :
Merupakan fungsi untuk kondisi perulangan, dimana 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)
Digunakan untuk :
Merupakan fungsi untuk kondisi percabangan jika hasil bagi variable p
tidak sama dengan 0.
§
Return(0); }
Digunakan untuk :
Merupakan fungsi untuk mengambil data masukkan untuk melanjutkan
eksekusi ke baris program berikutnya.
§ switch(ch){
case 1 : bfs(s,n);
goto a;
case 2 : dfs(s,n);
goto a;
case 3:
break;
}
return(0);
}
Digunakan
untuk :
Melakukan kondisi percabangan, dengan ketenetuan sbg berikut :
-
untuk pilihan pertama dari percabangan, dimana
program akan mengeksekusi blok procedure bfs.
-
pilihan kedua dari percabangan, dimana program akan
mengeksekusi blok procedure dfs.
-
berfungsi untuk pilihan ketiga jika angka yang kita
masukkan bukan 1 atau 2 maka program akan berhenti mengeksekusi,untuk mengambil
data masukkan untuk melanjutkan eksekusi ke baris program berikutnya.
-
berfungsi untuk kondisi perulangan, dimana
mengeksekusi dimulai dari bilangan 1, program akan berhenti mengeksekusi jika
variable i telah lebih besar daripada variable n.
serta variable i akan bertambah satu setiap terjadi perulangan, dan
kondisi percabangan jika hasil bagi variable p tidak sama dengan 0.
OUTPUT
