Contoh Program Algoritma DFS dan BFS Menggunakan C-Free/Turbo C

Assalamu’alaikum..

Dalam pembahasan sebelumnya saya telah membahas tentang Algoritma Brute Force Untuk Mencari Bilangan Dan Menyortir Bilangan. Pada pembahasan kali ini saya akan membahas tentang Membuat Program Algoritma DFS dan BFS Menggunakan C-Free/Turbo C.

Sedikit mengenai Algoritma BFS (Breadth First Search) dan DFS (Depth First Search) adalah Algoritma untuk mencari solusi agar lebih praktis. Perbedaan dari kedua algoritma tersebut adalah BFS jika solusi sudah ketemu maka percabangan yang lain dalam program harus diselesaikan terlebih dahulu, namun sebaliknya pada DFS, jika solusi sudah ketemu maka program selesai.

1. 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++)

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

2. Logika Program

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

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

=> Perintah Diatas digunakan untuk mendefinisikan prosedur antrian penuh

void bfs(int s, int n);

void dfs(int s, int n);

=> Perintah Diatas digunakan untuk perhitungan bfs dan perhitungan dfs.

void push(int item);

=> Perintah Diatas digunakan untuk jika terjadi kelebihan data .

main() {

=> Perintah Diatas digunakan untuk prosedur utama dalam program.

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

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

=> 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){

=> Perintah Diatas digunakan untuk kondisi percabangan

case 1:bfs(s,n);

=> Perintah Diatas digunakan untuk pilihan pertama dari percabangan, dimana program akan mengeksekusi blok procedure bfs.

case 2:dfs(s,n);

=> Perintah Diatas digunakan untuk pilihan kedua dari percabangan, dimana program akan mengeksekusi blok procedure dfs.

case 3: break; }

=> Perintah Diatas digunakan untuk pilihan ketiga jika angka yang kita masukkan bukan 1 atau 2, maka program akan berhenti mengeksekusi.

return(0); }

=> Perintah Diatas digunakan untuk mengambil data masukkan untuk melanjutkan eksekusi ke baris program berikutnya.

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

=> 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)

=> Perintah Diatas digunakan untuk kondisi percabangan jika hasil bagi variable p tidak sama dengan 0.

getch();

=> Perintah Diatas digunakan untuk membaca sebuah karakter, menampilkan karakter dari tombol yang ditekan, dan menunggu sembarang tombol ditekan.

3. Output

Pada BFS dan DFS

Mungkin itu saja pembahasan kali ini tentang Membuat Program Algoritma DFS dan BFS Menggunakan C-Free/Turbo C. mohon maaf apabila ada kata yang kurang berkenan dan salah, semoga bermanfaat.. terima kasih… ^^

Wassalamu’alaikum…

Download C-Free (Pro) : Disini Atau Disini

5 Responses to "Contoh Program Algoritma DFS dan BFS Menggunakan C-Free/Turbo C"

Andrekocak Blog1:29:00 am
Programming :D
kalo bahasa C++ atau #C ane blo ngedalemin gan
tapi kalo Web PRogramming
kaya Php,Perl,Ruby,HTML Nah ane udah sedikit-sedikit ngerti :p
Unknown3:47:00 pm
You da real MVP
Unknown7:32:00 pm
kang,.. cara buat lingkaran yg berwarna diagram venn dlm program C++ bgaimnana ya kang??
ainur10:29:00 am
(h) (h) (h) (h) (h) (h) (h) (h) (h) (h) (h) (h) (h) (h) (h) (h) (h) (h) (h) (h) (h)
ARIGATOU GOZAIMAZU