Implementasi Algoritma Depth First Search (DFS) dengan PHP - Elang Sakti
Download Ebook Belajar Arduino PDF, Arduino untuk pemula
Jasa Pembuatan Program Arduino, pemrograman Arduino
# Hack Your Skills! to be Professional Mechatronics

Implementasi Algoritma Depth First Search (DFS) dengan PHP

1 komentar
Pada tulisan ini kita akan ngobrol tentang apa itu DSF (Depth First Search) dan implementasinya. DFS merupakan algoritma dasar pada model pencarian Blind Search. Seperti yang kita bahas pada artikel terdahulu (Blind Search dan Heuristic Search), DFS termasuk ke dalam model pencarian apa adanya dan asal ketemu.

Pada DFS, semua kemungkinan akan dipetakan atau digenerate. Karena solusi yang akan dicapai berbentuk pohon solusi, maka alur pemetaannya adalah diambil dari yang terdalam. Proses pencariannya adalah kebawah dahulu, baru ke samping. Konsep ini kebalikan dari BFS (Breath First Search) yang proses pencariannya kesamping dulu, balu ke bawah (dalam).

Oke kita langsung implementasi dan analisa untuk membuktikan alurnya. Harapannya semoga kita semua lebih memahami bagaimana alur DFS dan menyelaraskan antara teori dan implementasinya. Untuk contohnya sederhana sih, kita membuat struktur organisasi, kemudian kita urutkan data pejabat dalam struktur tersebut menggunakan algoritnya DFS, kita urutkan posisinya sesuai dengan algortma DFS.

Perhatikan gambar berikut:

Source code Implementasi Algoritma Depth First Search (DFS) dengan PHP
Berdasarkan teori DFS, yang dicari berawal simpul terdalam / paling awal terlebih dahulu. Setelah itu merambat satu-persatu ke simpul paling ujung. Jadi model pnecariannya adalah menurun. Berbeda dengan BFS yang alur pencariannya menyamping. Alur pencarian pada struktur diatas adalah sebagai berikut:

  • Dari Agus, setelah dicek Agus ternyata mempunyai dua bawahan.
  • Periksa bawahan Agus yang pertama, namanya Novan, setelah dicek, Novan punya dua bawahan juga.
  • Periksa bawahan Novan yang pertama, namanya Syauqil, setelah dicek, Syauqil adalah posisi paling bawah / ujung.
  • Periksa bawahan Novan yang kedua, namanya Aji, setelah dicek, dia juga ada di posisi paling bawah sekaligus yang terakhir.
  • Berikutnya periksa bawahan Agus yang kedua, namanya Budi, setelah dicek, ternyata dia punya tiga bawahan.
  • Bawahan Budi yang pertama adalah Wildan dan dia tidak punya bawahan lagi (posisi paling bawah).
  • Bawahan Budi yang kedua adalah Ni'am dan dia juga ada di posisi paling bawah.
  • Bawahan Budi yang ketiga adalah Bayu dan dia juga di posisi paling bawah sekaligus akhir dari pencarian.
Script di bawah ini adalah contoh dari DFS yang dibuat dengan PHP. Data yang dipakai adalah data array yang sudah diatur seperti struktur jabatan. Data array ini juga bisa digantikan dengan database. Berikut hasil dari script di bawah ini:


<?php
/*     1
 *    / \
 *   2   3___
 *  / \  | \ \
 * 4   5 6  7 8
 *
 */

$ar[1]['parent']=0;
$ar[1]['value']=1;
$ar[1]['nama']='Agus';
$ar[1]['posisi']='Ketua';

$ar[2]['parent']=1;
$ar[2]['value']=2;
$ar[2]['nama']='Novan';
$ar[2]['posisi']='Wakil 1';

$ar[3]['parent']=1;
$ar[3]['value']=3;
$ar[3]['nama']='Budi';
$ar[3]['posisi']='Wakil 2';

$ar[4]['parent']=2;
$ar[4]['value']=4;
$ar[4]['nama']='Syauqil';
$ar[4]['posisi']='Anggota';

$ar[5]['parent']=2;
$ar[5]['value']=5;
$ar[5]['nama']='Aji';
$ar[5]['posisi']='Anggota';

$ar[6]['parent']=3;
$ar[6]['value']=6;
$ar[6]['nama']='Wildan';
$ar[6]['posisi']='Anggota';

$ar[7]['parent']=3;
$ar[7]['value']=7;
$ar[7]['nama']='Ni\'am';
$ar[7]['posisi']='Anggota';

$ar[8]['parent']=3;
$ar[8]['value']=8;
$ar[8]['nama']='Bayu';
$ar[8]['posisi']='Anggota';

function dfs($arr,$parent,$base){
 global $explc;
 global $explv;
 $explc++;

 for($a=1; $a<=count($arr); $a++){
  if($parent==0){
   $explv[$explc]['parent'] = $arr[$a-1]['parent'];
   $explv[$explc]['value'] = $arr[$a-1]['value'];
   $explv[$explc]['nama'] = $arr[$a-1]['nama'];
   $explv[$explc]['posisi'] = $arr[$a-1]['posisi'];

   $explv[$explc]['base'] = $base;
  }
  if($arr[$a]['parent']==$parent){
   $explv[$explc]['parent'] = $arr[$a]['parent'];
   $explv[$explc]['value'] = $arr[$a]['value'];
   $explv[$explc]['nama'] = $arr[$a]['nama'];
   $explv[$explc]['posisi'] = $arr[$a]['posisi'];

   $explv[$explc]['base'] = $base;
   $base++;
   dfs($arr,$arr[$a]['value'],$base);
   $base--;
  }
 }
}

function menjorok($jumlah,$tanda){
 for($a=0;$a<$jumlah;$a++) echo $tanda;
}

echo "\n";
global $explv,$explc;
$explc = -1;
dfs($ar,0,0);
 for($a=0; $a<$explc; $a++){
 echo menjorok($explv[$a]['base'],' ').$explv[$a]['nama']." (".$explv[$a]['posisi'].")\n";
}
unset($explc);
unset($explv);
?>

Implementasi Algoritma Depth First Search (DFS) dengan PHP

Selain ini, pada artikel Cara Mengatasi dan Membersihkan Virus Sality yang Menginveksi File htm/html juga disajikan implementasi DFS untuk meng-expand folder dan isinya.

Written by ElangSakti
Implementasi Algoritma Depth First Search (DFS) dengan PHP
Bahasan: Pada tulisan ini kita akan ngobrol tentang apa itu DSF (Depth First Search) dan   implementasinya. DFS merupakan algoritma dasar pada mod...
Published at Senin, 25 Februari 2013, Updated at Senin, 25 Februari 2013
Reviewed by dr. on
Rating: 4.7

1 komentar :

  1. bagus banget artikelnya, mas Hari Santoso mohon bantuannya: gimana mengimplementasikan DFS ini ke PHP-MySQl dengan soal kasus Bimbingan Konseling Siswa Bermasalah. Rootnya: sebab, Nodenya: Masalah dan Solusi, Terima kasih atas bantuannya

    BalasHapus