Teknik Informatika UNMUH Jember (1210651077)

Senin, 15 April 2013

Queue Array


package tugaskelompok;
class Queue {
    private int maxSize;
    private long[] queArray;
    private int front;
    private int rear;
    private int nItems;
//————————————————————–
    public Queue(int s) 
    {
        maxSize = s;
        queArray = new long[maxSize];
        front = 0;
        rear = -1;
        nItems = 0;
    }
//————————————————————–
    public void insert(long j) 
    {
        if (rear == maxSize - 1) //
        {
            rear = -1;
        }
        queArray[++rear] = j;         
        nItems++;                    
    }
//————————————————————–
    public long remove() 
    {
        long temp = queArray[front++]; 
        if (front == maxSize) //
        {
            front = 0;
        }
        nItems--;                     
return temp;
    }
//————————————————————–
    public long peekFront() //
    {
        return queArray[front];
    }
//————————————————————–
    public boolean isEmpty()
    {
        return (nItems == 0);
    }
//————————————————————–
    public boolean isFull() 
    {
        return (nItems == maxSize);
    }
//————————————————————–
    public int size() 
    {
        return nItems;
    }
//————————————————————–
--------------------------------------------------------------------------------
package tugaskelompok;
public class TestQueue {
    public static void main(String[] args) {
        Queue theQueue = new Queue(5);
        theQueue.insert(10);          
        theQueue.insert(20);
        theQueue.insert(30);
        theQueue.insert(40);
        theQueue.remove();              
        theQueue.remove();              
        theQueue.remove();
        theQueue.insert(50);           
        theQueue.insert(60);           
        theQueue.insert(70);
        theQueue.insert(80);
        while (!theQueue.isEmpty()) 
        {                           
            long n = theQueue.remove();  
            System.out.print(n);
            System.out.print(" ");
        }
        System.out.println("");
    }  
}  



Modul
Praktikum Struktur Data



Nur wihdatul Hasanah
1210651077

Universitas Muhammadiyah Jember
Teknik Informatika
2012 / 2013


BAB 1
Overview Struktur Data
Tujuan Pembelajaran
·         Mahasiswa memahami representasi data dan dapat mendeklarasikan struktur data secara lengkap

1.1     Pengenalan Struktur Data

        Dalam istilah ilmu komputer, sebuah struktur data adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien.
        Dalam teknik pemrograman, struktur data berarti tata letak data yang berisi kolom-kolom data, baik itu kolom yang tampak oleh pengguna (user) atau pun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna.Setiap baris dari kumpulan kolom-kolom tersebut dinamakan catatan (record).Lebar kolom untuk data dapat berubah dan bervariasi.Ada kolom yang lebarnya berubah secara dinamis sesuai masukan dari pengguna, dan juga ada kolom yang lebarnya tetap.Dengan sifatnya ini, sebuah struktur data dapat diterapkan untuk pengolahan database (misalnya untuk keperluan data keuangan) atau untuk pengolah kata (word processor) yang kolomnya berubah secara dinamis.Contoh struktur data dapat dilihat pada berkas-berkas lembar-sebar (spreadsheet), pangkal-data (database), pengolahan kata, citra yang dipampat (dikompres), juga pemampatan berkas dengan teknik tertentu yang memanfaatkan struktur data.

1.2     Pengenalan Algoritma

        Dalam matematika dan komputasi, algoritma atau algoritme[1] merupakan kumpulan perintah untuk menyelesaikan suatu masalah.Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik. Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.
   Desain dan analisis algoritma adalah suatu cabang khusus dalam ilmu komputer yang mempelajari karakteristik dan performa dari suatu algoritma dalam menyelesaikan masalah, terlepas dari implementasi algoritma tersebut.Dalam cabang disiplin ini algoritma dipelajari secara abstrak, terlepas dari sistem komputer atau bahasa pemrograman yang digunakan. Algoritma yang berbeda dapat diterapkan pada suatu masalah dengan kriteria yang sama.
        Kompleksitas dari suatu algoritma merupakan ukuran seberapa banyak komputasi yang dibutuhkan algoritma tersebut untuk menyelesaikan masalah.Secara informal, algoritma yang dapat menyelesaikan suatu permasalahan dalam waktu yang singkat memiliki kompleksitas yang rendah, sementara algoritma yang membutuhkan waktu lama untuk menyelesaikan masalahnya mempunyai kompleksitas yang tinggi.
Contoh :
Contoh :
·         ƒ Menghitung Luas persegi
Input  :  sisi
Output  : sisi*sisi
Algoritma mencari luas persegi :
Contoh kasus :  sisi=5
Metode : 5*5= 25 

1.3     Review

   Sebelum kita melangkahke bab berikutnya ada baiknya untuk mengingat kembali apa yang kita ketahui tentang bahasa pemrograman java yang telah di tempuh sebelumnya. Makaperlu untuk mereview sekilas tentang beberapa struktur bahasa pemrograman java yang akan sering kita gunakan nanti pada saat kuliah praktikum struktur data. Perhatikan dengan seksama tiap-tiap bagian struktur bahasa pemrograman java berikut ini.
1.3.1    Tipe Data
·         String, yakni suatu variabel yang menampung data kumpulan huruf atau karakter. Cara pendeklarasiannya sebagai berikut.String nama_var]=”[value]”;
Contoh :String alamat=”Jl. Sumatra 45”
·         Integer, suatu variabel yang menangani tipe data bilangan bulat. Cara pendeklarasiannya sebagai berikut.int [nama_var]=[value];
Contoh :int bilangan=300;
·         Boolean, adalah tipe data yag paling sederhana. Tipe data ini hanya berisi dua nilai yakni true atau false. Tipe data ini sering digunakan untuk menyatakan suatu kondisi. Cara pendeklarasiannya sebagai berikut. boolean [nama_var]=[value];
Contoh :boolean lulus=true;
·         Array adalah suatu struktur data dalam bentuk deret data. Jadi array menyimpan suatu himpunan data yang tersusun dalam bentuk deretan data. Dalam java array direpresentasikan dalam suatu varibel yang bernama variabel array. Ada dua cara mendeklarasikan variabel array. Cara pertama adalah dengan memberikan value pada saat kita mendeklarasikan variabel array. Perhatikan struktur pendeklarasiannya sebagai berikut:
<tipe_data>[]<nama_var>={<value1>,<value2>};
Contoh :String []data={“Susan”,”Santi”,”Santo”};
Kode diatas berarti kita membuat suatu variabel array yang bernama “data” dengan tipe data string yang berisikan tiga buah data yakni Susan, Santi, dan Santo.
Cara yang kedua adalah dengan tanpa melakukan inisaialisasi(pemberian value awal) terlebih dahulu tetapi jika kita melakukan cara ini maka kita diharuskan untuk mengisikan panjang array. Perhatikan struktur berikut.
<tipe_data>[]<nama_var>=new <tipe_data>[<panjang_array>];
Contoh :int[]bilangan=new int[100];
kode diatas berarti kita membuat suatu variabel array yang bernama “bilangan” dengan tipe data integer dan dengan panjang data 100.
1.3.2    Struktur Kontrol
·         Struktur percabangan:dalam java salah satunya direpresentasikan dalam suatu struktur “IF” yang biasanya dikombinasikan dengan “ELSE” apabila proses memiliki lebih dari satu cabang. Perhatikan struktur if-else berikut.
If(<kondisi>){
<statement 1>
}else{
<statement 2>
}
Penjelasan.
Kondisi: berisi suatu operasi(biasanya perbandingan) yang memberikan suatu nilai boolean yakni true atau false.
Statement 1: adalah suatu statement atau baris program yang akan dieksekusi apabila kondisi memberikan nilai true.
Statement 2: satement atau baris program yang akan dieksekusi apabila kondisi memberikan nilai false.
Perlu ditekankan disini bahwa apabila suatu kondisi telah memberikan nilai true maka statement 1 akan dieksekusi dan statement 2 akan diabaikan. Begitu pula apabila kondisi memberikan nilai false maka statemen 2 yang akan dieksekusi sedangkan statement 1 akan diabaikan. Perhatikan cantoh penerapannya dalam suatu class java.

·         Struktur Perulangan :Dalam bahasa pemrograman java struktur perulangan biasanya direpresentasikan dengan menggunakan struktur “FOR”. Blok kode yang berada pada kalang/scope for inilah yang akan dilakukan eksekusi berulang kali sesuai dengan kondisi tertentu. Perhatikan struktur for berikut.
for(<inisialisasi>;<kondisi>;<update>){
<statement>;
}
Penjelasan
Inisialisasi : berisi proses pemberian nilai awal pada variabel yang digunakan sebagai kontrol perulangan(biasanya variabel integer) contoh: int i = 0
Kondisi : beiasanya berisi proses pembandingan nilai variabel kontrol dengan nilai tertentu. Kondisi ini akan memberikan nilai boolean yakni true atau false. Contoh: i < 100
Update : berisi proses update nilai variabel kontrol. Update variabel kontrol ini digunakan agar suatu perulangan akan berhenti pada suatu kondisi tertentu. Update variabel ini biasanya menggunakan operasi increment dan decrement. Contoh: i++
1.3.3    Pemrograman Berorientasi Objek
      Method adalah suatu mekanisme yang digunakan untuk memparsialkan atau membagi suatu kode program menjadi beberapa kode program dengan proses yang spesifik. Misalkan kode program yang digunakan untuk mencetak output dikumpulkan dalam suatu method yang bernama method cetak. Secara umum ada dua macam method yakni method setter dan method getter.
·         Method Setter :Sesuai dengan namanya, method ini memang biasanya digunakan untuk merubah/ memanipulasi suatu nilai atau properti class. Jika kita melakukan pemanggilan method jenis ini maka method ini hanya mengeksekusi baris kode yang ada pada method tersebut tanpa adanya nilai balik yang didapatkan pada proses pemanggilannya.
Struktur method setter adalah sebagai berikut.
<access modifier> void <nama_method>(<parameter>){
<baris kode>
}
Penjelasan
Access modifier: ada beberapa beberapa hak akse method yang dikenal java, tetapi untuk praktikum ini kita cukup menggunakan access modifier public agar method dapat diakses oleh objek yang bersangkutan di class yang lain.
Parameter : dapat berisi beberapa deklarasi variabel yang dipisahkan dengan tanda koma(,).
Contoh: public void cetak(String nama)

·         Method getter :Berbeda dengan method setter yang hanya bisa mengeksekusi baris kode yang ada di dalamnya, method getter selain mengeksekusi baris kodenya juga memberikan nilai balik(getting value) kepada pemanggilnya. Perhatikan struktur method getter berikut.
<access modifier><tipe_data><nama_method> (<parameter>){
<baris kode>
return<value>;
}
Perbedaan mendasar dari struktur method setter dan getter yang pertama adalah pada method getter menggunakan tipe data seperti int, String bahkan juga bisa menggunakan tipe data objek, sedangkan untuk method setter hanya menggunakan keyword void saja. Perbedaan yang kedua adalah pada method getter terdapat keyword return yang berfungsi untuk memberikan nilai balik pada pemanggil method ini.
·         Constructor adalah suatu method khusus yang akan dijalankan pada saat pembuatan suatu objek. Dapat dikatakan bahwa dengan konstruktor inilah kita melakukan inisialisasi atau pemberian nilai awal dari objek yang kita ciptakan dari class yang bersangkutan. Berikut adalah ciri-ciri dari constructor yang membedakan dengan method biasa.
a.       Nama constructor sama dengan nama class
b.      Constructor tidak memiliki return value
c.       Acces modifiernya public
Constructor tidak dapat dipanggil secara  langsung, namun harus dipanggil dengan menggunakan operator new pada pembentukan sebuah class.
Struktur dasar constructor:
public  <nama_class>(<parameter>){
<baris_kode>;
}






BAB 2
Dasar – dasar Larik dalam Java
Tujuan Pembelajaran
·         Menjelaskan fitur-fitur teknologi dari java
·         Menjelaskan perbedaan fase pada pemrograman java


2.1   Mendeklarasikan Aray
        Array merupakan kemampuan  untuk menggunakan  satu  variabel  yang  dapat menyimpan  beberapa  data dan  memanipulasinya  dengan  lebih  efektif. Array  harus  dideklarasikan  seperti  layaknya  sebuah  variabel.  Pada  saat mendeklarasikan array,  anda harus membuat  sebuah daftar dari  tipe data,  yang diikuti oleh sepasang tanda kurung [], lalu diikuti oleh nama identifier-nya. Sebagai contoh,
        int []ages;
atau  Anda  dapat  menempatkan  sepasang  tanda kurung   [] sesudah nama identifier. Sebagai contoh,
        int ages[];

2.2   Aray Satu Dimensi
contoh program array satu diimensi:


Output :


3.2   Aray Dua Multidimensi
      Array  multidimensi  diimplementasikan  sebagai  array  yang  terl etak  di dalam  array.Array  multidimensi dideklarasikan  dengan menambahkan  jumlah  tanda  kurung  setelah nama array. Sebagai contoh,
int[][] twoD = new int[512][128];
char[][][] threeD = new char[8][16][24];
String[][] dogs = {{ "terry", "brown" },
{ "Kristin", "white" },
{ "toby", "gray"},
{ "fido", "black"}
};
       


        Contoh Program :
        Output :

4.2   Tipe Data Abstrak
        Tipe data abstrak (TDA) atau lebih dikenal dalam bahasa Inggris sebagai Abstract data type (ADT) merupakan model matematika yang merujuk pada sejumlah bentuk struktur data yang memiliki kegunaan atau perilaku yang serupa; atau suatu tipe data dari suatu bahasa pemrograman yang memiliki sematik yang serupa. Tipe data abstrak umumnya didefinisikan tidak secara langsung, melainkan hanya melalui operasi matematis tertentu sehingga membutuhkan penggunaan tipe data tersebut meski dengan resiko kompleksitas yang lebih tinggi atas operasi tersebut.
contoh tipe data abstrak :
·         Tipe jadi (built-in): boolean, integer, real, array, dll
·         Tipe buatan (user-defined): stack, queue, tree, dll



BAB 4
Rekursi
Tujuan Pembelajaran
·         Memahami konsep dari bilangan triangular dan faktorial
·         Mampu memahami dan mengimplementasikan konsep rekursi ke dalam program
·         Mampu memecahkan masalah sederhana menggunakan rekursi

4.1   Rekursi
        Rekursi adalah fungsi yang melakukan proses perulangan dengan cara memanggil dirinya sendiri. Selain itu Rekursi merupakan konsep pengulangan yang penting dalam ilmu komputer. Konsep ini dapat digunakan untuk merumuskan solusi sederhana dalam sebuah permasalahan yang sulit untuk diselesaikan secara iteratif dengan menggunakan loop for, while do. Pada saat tertentu konsep ini dapat digunakan untuk mendefinisikan permasalahan dengan konsisten dan sederhana. Pada saat yang lain, rekursi dapat membantu untuk mengekspresikan algoritma dalam sebuah rumusan yang menjadikan tampilan algoritma tersebut mudah untuk dianalisa.

4.2   Bilangan Triangular
        Bilangan triangular adalah bilangan yang didapatkan dari menambahkan n dengan bentuk sebelumnya. Dalam hal ini bilangan triangular ini menerapkan konsep rekursi.
Contoh : bilangan triangular dari 5 adalah 15
n=5 è n+(n-1) = 5+((5-1)) = 5 +(4+3+2+1)=15
berikut source bilangan triangular :


      Output :
4.3   Bilangan Faktorial
        Bilangan factorial sama konsepnya dengan bilangan triangular, kecuali bahwa yang digunakan adalah perkalian dan bukan penjumlahan. Bilangan factorial didapat dari perkalian n dengan bentuk sebelumnya.
Contoh : bilangan factorial dari 5 adalah 120
              n=5 è n*(n-1) = 5*(4!) = 5*(4*3*2*1) = 120
Berikut source dari bilangan Faktorial :
 

      Output :
       


BAB 5
Algoritma Pengurutan/Sorting
Tujuan Pembelajaran
·       Memahami konsep dari algoritma bubble sort
·       Memahami konsep dari algoritma quicksort
·       Memahami tentang perbandingan kinerja dari masing-masing algoritma sorting

5.1   Sorting
        Sorting adalah sebuah teknik pemrograman untuk mengurutkan suatu data. Teknik ini bisa menjadi langkah awal untuk uuntuk melakukan pencarian karena sebuah pencarian dari data yang telah diurutkan sangat lebih cepat  dibandingkan dengan pencarian linier. Banyak sekali teknik-teknik dari algooritma pencarian ini ,antara lain : Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Shellsort, Quicksort dan lain sebagainya. Namun dalam pertemuan kali ini kita akan membahas Bubble Sort dan Qiucksort saja.
5.2   Bubble Sort
        Bubble Sort adalah sebuah algoritma pengurutan yang  sangat lamban, tapi secara konseptual algoritma ini merupakan yang paling sederhana dan karena itu merupakan awal yang bagus untuk mengeksplorasi kita mengenai teknik pengurutan.
Berikut source dari Bubble Sort :
        Implementasi dari Class Bubble Sort  :
       
       


        Output :
5.3   Quicksort
        Quicksort adalah algoritma yang beroperasi dengan membagi sebuah larik/array ke dalam sub larik dan kemudian memanggil dirinya sendiri secara rekrusif. Kita harus memilih pivot untuk membagi ke dalam sub larik.
Berikut source Quicksort :
 






      Implementasi dari class QuickSort
       
        Output :

BAB 6
Stack dan Queue
Tujuan Pembelajaran
·         Mahasiswa memahami tentang stack dan queue
·         Mahasiswa dapat membuat suatu program menggunakan Stack dan Queue
·         Mahasiswa memahami perbedaan Stack dan Queue

6.1      Stack and Queue
        Struktur   kontrol  pemilihan adalah  pernyataan dari   Java  yang  mengijinkan  user  untuk memilih dan mengeksekusi blok kode spesifik dan mengabaikan blok kode yang lain. Stack adalah suatu bentuk khusus dari linear list di mana operasi penyisipan dan penghapusan atas elemen-elemennya hanya dapat dilakukan pada satu sisi saja yang disebut sebagai “TOP”. Cara ini dapat disebut dengan sistem LIFO (Last In First Out) yaitu item yang terakhir masuk merupakan item yang pertama keluar.
        Queue adalah suatu linear list di mana operasi DELETE terjadi pada sisi depan (FRONT) dan operasi INSERT terjadi pada sisi belakang (REAR). Jika diberikan suatu Queue Q dengan elemen-elemennya yang terdiri atas Q1, Q2, ....., QT maka queue Q dituliskan Q = [ Q1, Q2, .........., QT ]
FRONT(Q) = Q1                        
REAR(Q) = QT
Selanjutnya untuk menyatakan jumlah elemen dalam suatu queue Q digunakan notasi NOEL(Q).

6.2   Stack
Misal diberikan Stack S sebagai berikut :
S = [ S1, S2, .........., ST ] à  maka TOP(S) = ST
Untuk menunjukkan jumlah elemen suatu stack digunakan notasi NOEL. Dari stack di atas, maka NOEL(S) = T.Selanjutnya, jika diberikan sebuah stack S = [A,B,C,D], maka stack S ini dapat digambarkan sebagai berikut :

 



Ada empat operasi dasar yang didefinisikan pada stack, yaitu :
o   CREATE(stack)
o   ISEMPTY(stack)
o   PUSH(elemen,stack)
o   POP(stack
      Berikut source Dari Stack:
    
    
    
     Implementasi dari class Tumpukan :
     
      Output :

6.3   Queue
Untuk menggambarkan suatu queue dapat dilakukan beberapa cara , Misal : diberikan Queue Q = [A, B, C, D, E, F], maka Queue Q dapat digambarkan sebagai berikut :
A
B
C
D
E
F

F
E
D
C
B
A

atau dapat pula digambarkan dengan posisi tegak.Prinsip kerja Queue adalah FIFO (First In First Out), di mana data yang masuk terlebih dahulu akan keluar pertama.
Terdapat empat operasi dasar yang didefinisikan pada queue, yaitu :
·         CREATE
·         ISEMPTY
·         INSERT
·         REMOVE
Berikut source dari queue :
     
     
        

   

           


            Implementasi class Queue :
           
            Output :




BAB 9
Senarai/List
Tujuan Pembelajaran
·         Memahami perbedaan array dan list
·         Memahami konsep dasar list
·         Mampu mengimplementasikan list dalam program

9.1   Pengertian List
        Senarai(list) adalah struktur data/ADT yang mendasar, yang seringkali digunakan untuk menyimpan koleksi dari data-data dan digunakan pada implementasi program computer sehingga masuk akal kalau kita saat ini harus membahas ADT List. ADT List dapat digunakan sebagai basis untuk mengimplementasikan ADT-ADT lainnya. ADT list dapat dianggap bangunan dasar untuk mengembangkan ADT lain yang lebih rumit.

9.2   Single Linked List
        Dalam contoh program ini kita akan membuat beberapa class untuk pengimplementasian list pada program.
Class Node :
Class LinkedList :


Output :
9.3   Double Linked List
        Sama seperti Single linked list , disini kita akan membuat beberapa class .
        Class pTwoChildNode :
       


       
        Class pDoublyLinkedList :
       
           
           
                       
       
Class berikutnya TestDouleLinkedList digunakan untuk mengimplementasikan clas-clas yang telah kita buat .


    Output :

BAB 10
Binary Tree
Tujuan Pembelajaran
·         Mahasiswa memahami tentang binary Tree
·         Mahasiswa memahami konsep tree
·         Mahasiswa mampu mengimplementasikan tree dalam sebuah program


10.1 Apa itu tree?
      Tree merupakan salah satu bentuk struktur data bukan linier yang menggambarkan bentuk hierarki antara elemen-elemen.Tree biasanya terdiri dari root (akar) dan node-node (simpul-simpul) yang berada di bawah root. Struktur seperti tree sangat banyak sekali dgunakan dalam dunia nyata, misalnya: struktur organisasi suatu perusahaan, pengaturan filesystem, daftar isi sebuah buku, dan masih banyak lagi.  Ilustrasi struktur data tree:
     Degree (derajat) adalah jumlah edge yang keluar dan masuk dari sebuah node.Contoh : node E memiliki in degree 1 dan out degree 2  Root (akar) adalah node yang memiliki derajat keluar >=0 dan derajat masuk = 0. Contoh : node A adalah root Subtree / child adalah bagian salah satu node dibawah root sampai ke bawah. Contoh : tree C adalah right subtree dari A dan tree B merupakan left subtree dari A  node G dan F merupakan child dari node C node F merupakan parent dari node J dan K Ancestor  adalah Node yang berada di atas node lain.

10.2    Contoh Program
          


             


Output :
                                        



BAB 11
Pencarian Data Dalam Array
Tujuan Pembelajaran
·         Mahasiswa memahami tentang konsep searching
·         Mahasiswa memahami algoritma dari searching
·         Mahasiswa mampu mengimplementasikan algoritma searching dalam sebuah program


11.1    Sekuensial Search
    Sequential search / pencarian beruntun atau banyak pula yang menyebutnya linear search (pencarian lurus), adalah salah satu metode algoritma pencarian yang paling sederhana. Para programmer pemula pasti akan menggunakan algoritma ini saat menghadapi kasus pencarian untuk pertama kali. Konsep dari algoritma ini tak terlalu sulit, yakni seluruh data akan dicek satu persatu sampai data yang dicari ditemukan.
     Ada 2 macam pencarian beruntun,yaitu pencarian pada array yang sudah terurut, dan pencarian pada array yang belum terurut.
11.2    Pencarian Dalam Array Acak
           Contoh program :
          
            Output :
           
11.3     Pencarian Dalam Array Acak
            Contoh program :
           


Output :
Perbedaan dari kedua metode diatas adalah ketika kita mencari data pada array yang acak itu memakan waktu yang lebih lama dalam proses pencariannya contohnya pada program diatas kita akan mencari data 2, pada pencarian array yang acak data 2 ditemukan pada indeks ke tiga sedangkan jika kita mengurutkanya dulu yaitu pada metode pencarian terurut maka data 2 ditemukan pada indeks ke dua
BAB 12
GRAPH
Tujuan Pembelajaran
·         Menangani exeption menggunakan blok tyr-catch-finally Mahasiswa memahami konsep dari graph
·         Mahasiswa memahami konsep dari algoritma DFS (Depth First Search)
·         Mahasiswa memahami konsep dari Algoritma (Breadth-First-serch)

12.1    Graph
   Algoritma DFS (Depth First Search) merupakan salah satu jenis algoritma greedy yang digunakan untuk men-scan karakter yang ada pada sebuah petak.Penerapan algoritma ini cukup banyak digunakan pada bidang sains dan teknologi, terutama pada piranti cerdas.Penjelasan algoritma DFS bisa dibaca di Wikipedia – Depth First Search.Penerapan dalam source code, algoritma DFS bisa menggunakan fungsi rekursi yang memanggil dirinya sendiri ataupun menggunakan stack (tumpukan).Salah satu penggunaan algoritma DFS adalah digunakan untuk permainan tebak jumlah dadu.
   Algoritma Breadth-first searchadalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada arasd dikunjungi lebih dahulu sebelum simpul-simpul pad aras d+1. Algoritma ini memerlukan sebuah antrian q untuk menyimpan simpul yang telah dikunjungi.Simpulsimpul ini diperlukan sebagai acuan untuk mengunjungi simpul-simpul yang bertetanggaan dengannya.Tiap simpul yang telah dikunjungu masuk ke dalam antrian hanya satu kali. Algoritma ini juga membutuhkan table Boolean untuk menyimpan simpul yang te lah dikunjungi sehingga tidak ada simpul yang dikunjungi lebih dari satu kali.



12.2   Algoritma DFS (Depth First Search)
Berikut source dari Algoritma (Depth-first-search):
Class DFSVertex :
Class DFSGraph :
 


Class DFSStack :
  Implementasi dari class-class yang kita buat :
Output :
12.3   Algoritma Breadth-first search
  Berikut source Algoritma (Breadth-First-serch) :
          

          

         


 

           Output :