Laporan Akhir Lab TI Perancangan & Analisis Algoritma Pertemuan 4 Algoritma BFS dan DFS
Listing Program
#include <stdio.h>
#include <conio.h>
#include <stdlib.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); }}
Logika Program
#include<stdio.h>
#include<conio.h>
#include <stdlib.h>
Fungsi perintah diatas digunakan sebagai standard library yang berfungsi untuk I/O package. Maksudnya agar 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. library pada C yang digunakan untuk mengkoneksikan pernyataan clrscr() dengan program yang kita buat.
void add(int item);
Fungsi perintah diatas digunakan untuk mendefinisikan prosedur antrian penuh.
void bfs(int s, int n);
void dfs(int s, int n);
Fungsi perintah piatas digunakan untuk perhitungan bfs dan perhitungan dfs.
void push(int item);
Fungsi perintah diatas digunakan untuk jika terjadi kelebihan data .
main() {
Fungsi perintah diatas digunakan untuk prosedur utama dalam program.
clrscr();
Fungsi perintah diatas digunakan untuk membersihkan layar ketika program dieksekusi.
int n,i,s,ch,j;
Fungsi perintah diatas digunakan untuk mendeklarasikan variable n, i, s, ch dan j yang bertipe data integer (bilangan bulat).
printf("matriks adjasensi\n ");
Fungsi perintah diatas digunakan untuk mencetak tulisan matriks adjasensi. Pernyataan \n digunakan agar tulisan utama yang dicetak ada jedanya (enter) pada saat program dieksekusi.
scanf("%d",&n);
Fungsi perintah diatas digunakan untuk menyimpan angka yang kita input ketika program dieksekusi. Disini terdapat %d yang mengartikan data inputan akan ditampilkan dalam bentuk decimal.
switch(ch){
Fungsi perintah diatas digunakan untuk kondisi percabangan.
case 1:bfs(s,n);
Fungsi perintah diatas digunakan untuk pilihan pertama dari percabangan, dimana program akan mengeksekusi blok procedure bfs.
case 2:dfs(s,n);
Fungsi perintah diatas digunakan untuk pilihan kedua dari percabangan, dimana program akan mengeksekusi blok procedure dfs.
case 3: break; }
Fungsi perintah diatas digunakan untuk pilihan ketiga jika angka yang kita masukkan bukan 1 atau 2, maka program akan berhenti mengeksekusi.
return(0); }
Fungsi perintah diatas digunakan untuk mengambil data masukkan untuk melanjutkan eksekusi ke baris program berikutnya.
for(i=1;i<=n;i++) {
Fungsi perintah diatas digunakan 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)
Fungsi perintah diatas digunakan untuk kondisi percabangan jika hasil bagi variable p tidak sama dengan 0.
getch();
Fungsi perintah diatas digunakan untuk membaca sebuah karakter, menampilkan karakter dari tombol yang ditekan, dan menunggu sembarang tombol ditekan.
BFS dan DFS merupakan jenis dari metode pencarian solusi. BFS merupakan metode pencarian solusi dimana 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 1 dari kiri ke kanan, kemudian berpindah ke level berikutnya dari kiri ke kanan hingga solusi ditemukan. DFS merupakan metode pencarian solusi dimana Proses pencarian dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini diulangi terus hingga ditemukannya solusi.
Dalam program ini, kita akan membuat pencarian BFS dan DFS dengan bantuan matriks. Program akan meminta inputan ordo dari matriks. Jika angka 2 dimasukkan, maka program akan memproses matriks 2 X 2. Setelah memasukan 2, maka program akan meminta elemen dari matriks tersebut, apabila kita memasukan 1 2 3 dan 4, program akan berlanjut pada proses percabangan, apakah akan memilih menu DFS atau BFS, ketika kita memilih DFS, program akan meminta simpul sumber, simpul sumber ini merupakan solusi yang akan dicari, ketika kita memasukan angka 2, maka yang tercetak 1 dan 2, secara BFS pun demikian, namun apabila kita memasukan angka 1, maka program tak akan memproses, ini dikarenakan program tidak menemukan solusi karena kita memasukan angka 2.
Output
Belum ada Komentar untuk "Laporan Akhir Lab TI Perancangan & Analisis Algoritma Pertemuan 4 Algoritma BFS dan DFS"
Posting Komentar