Senin, 15 April 2013
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 :
Langganan:
Postingan (Atom)