·
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 Program :
Pada
laporan akhir PAA yang ke-4 ini saya akan mencoba membahas tentang 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>
-
Jika kita menginginkan
penggunaan input dan output, kita harus menyertakan library ini karena kalau
kita tidak menggunakan library ini, maka kita tidak bisa menggunakan perintah
input dan output dalam program yang kita buat.
#include
<conio.h>
-
Pernyataan yang digunakan
untuk mengkoneksikan pernyataan ‘clrscr()’ dengan program yang kita buat. Tanpa
menggunakan library ini, kita tidak bisa menggunakan fungsi prototype seperti :
gotoxy(), clrscr().
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:
DestroyWindow(GetActiveWindow());
-
Untuk menutup atau mengeluarkan program.
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
Output :
Tidak ada komentar:
Posting Komentar