Implementasi Algoritma Depth-First. Studi Kasus : Melihat Histori dari Order (menggunakan PHP)

Berikut ini adalah implementasi dari salah satu algoritma pencarian pada pohon (search tree algorithm), yaitu Depth-First Algorithm. Depth-First Algorithm adalah algoritma yang mendahulukan mencari node pada level terbawah.

Kasus :

Pada suatu firma arsitektur, untuk membuat suatu rumah, firma ini memungkinkan para pelanggannya untuk memodifikasi (mengubah) detail dari pesanan(order) yang sudah disepakati sebelumnya. Modifikasi ini nantinya bisa batal (tidak jadi dilakukan),  bisa pula dikerjakan lalu dimungkinkan untuk dilakukan modifikasi kembali dikemudian hari (status).

Pemilik firma ingin melihat histori dari suatu order. Mulai dari order awalnya (root) sampai dengan order terakhir. Termasuk order-order yang batal.

Solusi :

Gambaran Algoritma

  1. Simpan order inputan.
  2. Cari root-node-nya (titik teratas dari pohon => order paling awal). Simpan dalam array.
  3. Gunakan algoritma Depth-First untuk mencari child-node (order-order anaknya) dari root-node. Simpan dalam array.
  4. Tampilkan array sesuai dengan level tiap node.

Contoh Tree :

Contoh Tree

Output :

Inputed Order = F

Inputed Order = L (beda Tree)

THE Code :

<?php
/*
 * Main Part of File.
 * Created by : Putri Chairina
 * 21 April 2010
 */
mysql_connect("localhost", "username", "password");
mysql_select_db("treesearch");

$nsorderInputed = "F";
echo "Inputed Order = ".$nsorderInputed."<br/>";
$result = mysql_query("SELECT * FROM maintable where nsorder = '$nsorderInputed'");

//masukkan array hasil pencarian.
$result = mysql_fetch_array($result, MYSQL_ASSOC);

//cari nsorder Root.
$theRoot = searchRoot($result['nsorder'],$result['prevorder']);
echo "Root Order = ".$theRoot."<br/><br/>";

//nsorder Root ditemukan. Simpan dalam array.
mysql_connect("localhost", "username", "password");
mysql_select_db("treesearch");
$query = "SELECT * FROM maintable where nsorder = '$theRoot'";
$result = mysql_query($query);
$row = mysql_fetch_array($result, MYSQL_ASSOC);
settype($stackArray, 'array');
$stackArray[0]["nsorder"] = $row['nsorder'];
$stackArray[0]["prevorder"] = $row['prevorder'];
$stackArray[0]["userstatus"] = $row['userstatus'];

//cari di kedalaman. (DepthFirst)
settype($stackResult, 'array');
$stackResult = searchDepth($stackArray[0]['nsorder'], $stackArray );

//tampilkan.
showRoot($stackResult, $theRoot);
showChildNode($stackResult, $nsorderInputed, $theRoot, 0);
?>

Fungsi searchRoot => Cari Root-Node

<?php
/*
 * function searchRoot.
 * Berfungsi untuk mencari node root dari suatu
 * node inputan.
 * Output = $tempRoot.
* Created by : Putri Chairina
* 21 April 2010
*/
function searchRoot($nsorder, $prevorder){
 mysql_connect("localhost", "username", "password");
 mysql_select_db("treesearch");
 //cari ke atas.
 $rootQuery = "SELECT * FROM maintable where nsorder = '$prevorder'";
 $result = mysql_query($rootQuery);
 $tempRoot = $nsorder;
 while($row = mysql_fetch_array($result, MYSQL_ASSOC)){
 $tempRoot = searchRoot($row['nsorder'],$row['prevorder']);
 }
 return $tempRoot;
}
?>

Fungsi searchDepth => Depth-First Algorithm

<?php
/*
 * function searchDepth.
 * Fungsi rekursif, implementasi algoritma Depth-First,
 * untuk mencari node-node yang berada di bawah level
 * node inputan($prevorderToBeSearch).
 * Output : $stackArray.
* Created by : Putri Chairina
* 21 April 2010
 */
function searchDepth($prevorderToBeSearch, $stackArray){
 mysql_connect("localhost", "username", "password");
 mysql_select_db("treesearch");
 //cari ke kedalaman.
 $length = sizeof($stackArray);
 $depthQuery = "SELECT * FROM maintable where prevorder = '$prevorderToBeSearch'";
 $result = mysql_query($depthQuery);

 while($row = mysql_fetch_array($result, MYSQL_ASSOC)){
 //tambahkan hasil ke dalam stack-array.
 $stackArray[$length]["nsorder"] = $row['nsorder'];
 $stackArray[$length]["prevorder"] = $row['prevorder'];
 $stackArray[$length]["userstatus"] = $row['userstatus'];
 //lakukan pencarian ke kedalaman berikutnya.
 $stackArray = searchDepth($row['nsorder'], $stackArray);
 $length =  sizeof($stackArray);
 }
 return $stackArray;
}
?>

Fungsi showRoot => Tampilkan root-node

<?php
/*
 * function showRoot.
 * Dibuat untuk mengambil value2 dari array yang
 * merupakan node Root(jika nanti dibutuhkan).
* Created by : Putri Chairina
* 21 April 2010
 */
function showRoot($arrayResult, $rootOrder){
 foreach($arrayResult as $key=>$value){
 if($value['nsorder']==$rootOrder){
 echo $value['nsorder']."<br/>";
 }
 }
}
?>

Fungsi showChildNode => Menampilkan child-node sesuai dengan level kedalamannya

<?php
/*
 * function : showChildNode.
 * Fungsi rekursif yang akan menampilkan node sesuai
 * dengan level kedalamannya.
* Created by : Putri Chairina
* 21 April 2010
 */
function showChildNode($arrayResult, $nsorderInputed, $rootOrder, $level){
 $level++;
 foreach($arrayResult as $key=>$value){
 if($value['prevorder']==$rootOrder){
 for($i = 0; $i<$level; $i++){
 echo "--- ";
 }
 if($value['nsorder']==$nsorderInputed){
 echo "<b>".$value['nsorder']."</b><br/>";
 }else{
 echo $value['nsorder']."<br/>";
 }
 showChildNode($arrayResult, $nsorderInputed, $value['nsorder'], $level);
 }
 }
}
?>

Database (MySQL)

-- MySQL dump 10.13  Distrib 5.1.37, for debian-linux-gnu (i486)
--
-- Host: localhost    Database: treesearch
-- ------------------------------------------------------
-- Server version    5.1.37-1ubuntu5.1

/*!40101 SET @OLD_CHARACTER_SET_CLIENT=@@CHARACTER_SET_CLIENT */;
/*!40101 SET @OLD_CHARACTER_SET_RESULTS=@@CHARACTER_SET_RESULTS */;
/*!40101 SET @OLD_COLLATION_CONNECTION=@@COLLATION_CONNECTION */;
/*!40101 SET NAMES utf8 */;
/*!40103 SET @OLD_TIME_ZONE=@@TIME_ZONE */;
/*!40103 SET TIME_ZONE='+00:00' */;
/*!40014 SET @OLD_UNIQUE_CHECKS=@@UNIQUE_CHECKS, UNIQUE_CHECKS=0 */;
/*!40014 SET @OLD_FOREIGN_KEY_CHECKS=@@FOREIGN_KEY_CHECKS, FOREIGN_KEY_CHECKS=0 */;
/*!40101 SET @OLD_SQL_MODE=@@SQL_MODE, SQL_MODE='NO_AUTO_VALUE_ON_ZERO' */;
/*!40111 SET @OLD_SQL_NOTES=@@SQL_NOTES, SQL_NOTES=0 */;

--
-- Table structure for table `maintable`
--

DROP TABLE IF EXISTS `maintable`;
/*!40101 SET @saved_cs_client     = @@character_set_client */;
/*!40101 SET character_set_client = utf8 */;
CREATE TABLE `maintable` (
 `nsorder` varchar(3) NOT NULL,
 `prevorder` varchar(3) NOT NULL,
 `userstatus` varchar(30) NOT NULL
) ENGINE=InnoDB DEFAULT CHARSET=latin1;
/*!40101 SET character_set_client = @saved_cs_client */;

--
-- Dumping data for table `maintable`
--

LOCK TABLES `maintable` WRITE;
/*!40000 ALTER TABLE `maintable` DISABLE KEYS */;
INSERT INTO `maintable` VALUES ('A','','tes'),('B','A','tesB'),('C','A','tesC'),('D','A','tesD'),('E','B','tesE'),('F','B','tesF'),('G','D','tesG'),('H','D','tesH'),('I','A','tesI'),('J','E','tesJ'),('K','','tes K'),('L','K','tes L');
/*!40000 ALTER TABLE `maintable` ENABLE KEYS */;
UNLOCK TABLES;
/*!40103 SET TIME_ZONE=@OLD_TIME_ZONE */;

/*!40101 SET SQL_MODE=@OLD_SQL_MODE */;
/*!40014 SET FOREIGN_KEY_CHECKS=@OLD_FOREIGN_KEY_CHECKS */;
/*!40014 SET UNIQUE_CHECKS=@OLD_UNIQUE_CHECKS */;
/*!40101 SET CHARACTER_SET_CLIENT=@OLD_CHARACTER_SET_CLIENT */;
/*!40101 SET CHARACTER_SET_RESULTS=@OLD_CHARACTER_SET_RESULTS */;
/*!40101 SET COLLATION_CONNECTION=@OLD_COLLATION_CONNECTION */;
/*!40111 SET SQL_NOTES=@OLD_SQL_NOTES */;

-- Dump completed on 2010-04-21 10:56:57

Referensi :

Download file

Jika user 4shared saya masih aktif :mrgreen: , rekan-rekan dapat mengunduh file PHP dan export database MySQL pada :

File index.php : http://www.4shared.com/file/_SI2klSU/treesearch.html

Hasil export database MySQL : http://www.4shared.com/document/fVbJrtxW/treesearch.html

Materi

http://en.wikipedia.org/wiki/Depth-first_search

Semoga bermanfaat.^^

Iklan

15 thoughts on “Implementasi Algoritma Depth-First. Studi Kasus : Melihat Histori dari Order (menggunakan PHP)

  1. hmmm, bagusss”, kebetulan juga sesuai dengan tugasku…
    tapi bisa upload file export.a dalam bentuk sql nggak, minta tolong nihhh……???

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s