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
EmoticonEmoticon