modul struktur data - repository.bsi.ac.id · single linked list (non circular), stack, queue,...
TRANSCRIPT
MODUL
STRUKTUR DATA
Disusun Oleh :
Nur Hidayati, M.Kom (200309005)
Program Studi Manajemen Informatika
Akademi Manajemen Informatika dan Komputer
Bina Sarana Informatika Jakarta
2016
ii
KATA PENGANTAR
Alhamdulillah, pertama penulis mengucapkan rasa syukur dan segala puji kepada
Allah SWT yang telah melimpahkan segala Rahmat dan KaruniaNYA, sehingga modul
Struktur Data ini dapat diselesaikan. Modul Struktur Data ini diharapkan dapat
mendukung mahasiswa dalam memahami matakuliah Struktur Data. Modul ini dibuat
berdasarkan sumber-sumber yang sudah banyak digunakan. Pada modul ini membahas
mengenai konsep Struktur Data secara umum. Modul ini membahas mengenai Konsep
Struktur Data & Array, Sistem Bilangan, Representasi Data, Array Dimensi Banyak,
Single Linked List (Non Circular), Stack, Queue, Struktur Pohon & Kunjungan Pohon
Biner, dan Graph . Akhir kata, penulis menyampaikan terimakasih yang tulus kepada
pihak-pihak yang telah memberikan bantuan dan dukungannya sehingga penulis dapat
menyelesaikan penulisan modul ini. Pada akhir kata, penulis memohon maaf yang
sebesar-besarnya jika dalam penulisan modul ini masih banyak kekurangan dan
kelemahannya. Penulis memohon adanya sumbangan ide, kritik dan saran untuk
perbaikan penulisan modul ini supaya lebih baik ke depannya.
iii
DAFTAR ISI
KATA PENGANTAR ............................................................................................................. ii
DAFTAR ISI............................................................................................................................iii
BAB I KONSEP STRUKTUR DATA & ARRAY .............................................................. 1
1.1 Pengertian Struktur Data ....................................................................................... 1
1.2 Konsep Dasar Tipe Data......................................................................................... 1
1.3 Konversi Bilangan ................................................................................................... 8
1.4 Array ........................................................................................................................ 9
BAB II SISTEM BILANGAN .............................................................................................. 16
2.1 Konsep Dasar Sistem Bilangan ............................................................................ 16
2.2 Satuan Data ........................................................................................................... 18
2.3 Sistem Pengkodean ............................................................................................... 19
2.4 Konversi Bilangan ................................................................................................. 21
BAB III REPRESENTASI DATA ....................................................................................... 27
3.1 Pengertian Representasi Data .............................................................................. 27
3.2 Representasi Integer ............................................................................................. 28
3.3 Penjumlahan Biner ............................................................................................... 30
BAB IV ARRAY DIMENSI BANYAK ............................................................................... 33
4.1 Array Dimensi Tiga (Three Dimensional Array) ............................................... 33
4.2 Tringular Array .................................................................................................... 35
BAB V SINGLE LINKED LIST (NON CIRCULAR)....................................................... 37
5.1 Konsep Pointer dan Linked List .......................................................................... 37
5.2 Pointer .................................................................................................................... 37
5.3 Linked List ............................................................................................................. 38
5.4 Single Linked List Non Circular .......................................................................... 40
5.5 Single Linked List Non Circular Menggunakan Head ...................................... 41
5.6 Menampilkan Isi Linked List............................................................................... 47
5.7 Singled Linked List Non Circular Menggunakan Head dan Tail .................... 48
BAB VI STACK ATAU TUMPUKAN ............................................................................... 54
6.1 Pengertian Stack atau tumpukan ........................................................................ 54
iv
6.2 Operasi Stack atau Tumpukan ............................................................................ 54
BAB VII QUEUE (ANTRIAN) ............................................................................................ 59
7.1 Pengertian Queue (Antrian) ................................................................................. 59
7.2 Deklarasi Queue .................................................................................................... 59
7.3 Operasi Pada Queue ............................................................................................. 60
BAB VIII STRUKTUR POHON & KUNJUNGAN POHON BINER ............................. 64
8.1 Pengertian Tree (Pohon) ...................................................................................... 64
8.2 Isilah Dasar dalam Pohon .................................................................................... 64
8.3 Isilah-Istilah dalam Pohon ................................................................................... 64
8.4 Sifat Utama Pohon Berakar ................................................................................. 66
8.5 Pohon Biner (Binary Tree) ................................................................................... 69
8.6 Istilah-istilah Pada Pohon Biner .......................................................................... 70
8.7 Deklarasi Pohon Biner .......................................................................................... 72
8.8 Penyajian Pohon Biner ......................................................................................... 72
BAB IX KUNJUNGAN PADA POHON BINER ............................................................... 74
9.1 Kunjungan Pada Pohon Biner ............................................................................. 74
9.2 Kunjungan Secara PreOrder (Depth First Order) ............................................... 74
9.3 Kunjungan Secara InOrder (Symetric Order)................................................... 76
9.4 Kunjungan PostOrder .......................................................................................... 77
9.5 Kunjungan Level Order ....................................................................................... 78
9.6 Aplikasi Pohon Biner ............................................................................................ 78
BAB X GRAPH DAN MATRIK PENYAJIAN GRAPH .................................................. 80
10.1 Graph ................................................................................................................. 80
10.2 Graph Berlabel .................................................................................................. 82
10.3 Derajat Graph ....................................................................................................... 83
10.4 Multigraph ............................................................................................................. 84
10.5 Keterhubungan ..................................................................................................... 84
10.6 Graph Terarah (Directed Graph / DiGraph) ..................................................... 87
10.7 Graph Tidak Terarah (Undirect Graph) ............................................................ 88
10.8 Critical Path .......................................................................................................... 88
10.9 Minimum Spanning Tree ..................................................................................... 89
10.10 Matriks Penyajian Graph ................................................................................ 89
v
DAFTAR PUSTAKA ............................................................................................................ 93
1
BAB I
KONSEP STRUKTUR DATA & ARRAY
1.1 Pengertian Struktur Data
Struktur Data adalah : suatu koleksi atau kelompok data yang dapat
dikarakteristikan oleh organisasi serta operasi yang didefinisikan terhadapnya.
Pemakaian Struktur Data yang tepat didalam proses pemrograman, akan menghasilkan
Algoritma yang lebih jelas dan tepat sehingga menjadikan program secara keseluruhan
lebih sederhana.
1.2 Konsep Dasar Tipe Data
Pada garis besarnya, Data dapat dikategorikan menjadi :
1. Type Data Sederhana / Data Sederhana
Terdiri dari :
a. Data Sederhana Tunggal
Misalnya : Integer, Real/Float, Boolean dan Character
1) Integer
Merupakan Bilangan Bulat dan tidak mengandung pecahan. seperti :
...-3,-2,-1,0,1,2,3,....
2
2) Real/Float
Type data yang merupakan bilangan pecahan. Jenis Data float ditulis
dgn menggunakan titik(koma) desimal. Misalnya : 0.32 4,35 -131.128
Type Real dapat juga ditulis dengan Rumus :
M = Pecahan, R = Radix,
e = Exponen, X = Hasil Bilangan,
Misalnya : 3.2 * 10-1 = 0.32
4.35 * 102 = 435
3) Boolean
Type data yang hanya mempunyai dua bentuk keluaran yaitu nilai
True dan False (Benar dan Salah) yang dinyatakan dengan 1 dan 0,
Sehingga satuan data yang terpakai cukup satu bit saja. Operator yang
digunakan adalah : And, Or dan Not.
3
4) Character
Type data yang terdiri dari aksara (simbol) yang meliputi digit
numerik, character alfabetik dan special character. Untuk menuliskan
tipe char, karakter perlu ditulis di dalam tanda petik tunggal ( ‘ ).
Contoh :
‘A’ _ karakter berupa huruf A
‘1’ _ karakter berupa angka 1
‘*’ _ karakter 3ymbol *
b. Data Sederhana Majemuk
Misalnya : String
String merupakan type data majemuk yang terbentuk dari kumpulan
character sebanyak 256 (default) dengan jangkauan niai 0 - 255. Kumpulan
character yang digunakan untuk membentuk String dinamakan alfabet.
Pemberian nilai String diapit dengan tanda petik ganda (“). Bentuk umum
penulisan tipe data ini adalah : tipe_data pengenal [panjang] ;
pengenal = nama variabel
panjang = bilangan bulat yg menunjukan jumlah karakter
Contoh : char nama[15] ;
Fungsi pada Operasi STRING
1) Strcpy()
Digunakan untuk menyalin nilai string.
Contoh menggunakan program C++:
4
#include <iostream.h>
#include <conio.h>
#include <string.h>
#include <stdio.h>
main()
{
char asal[100];
char hasil[100];
clrscr();
cout<<"Masukan kalimat : "; gets(asal);
strcpy(hasil,asal);cout<<endl;
cout<<"Kalimat asal : "<<asal<<endl;
cout<<"Kalimat hasil : "<<hasil<<endl;
getch(); }
Hasil Tampilan dari Program diatas sebagai berikut :
2) Strcat
Digunakan untuk menggabungkan nilai string.
Contoh menggunakan program c++:
int main() {
char string1 [] ="Belajar";
char string2 [] ="Logika Algortima";
cout<<"Menggabungkan String"<<endl;
cout<<"--------------------"<<endl;
cout<<"string1 : "<<string1<<endl;
cout<<"string2 : "<<string2<<endl;
strcat(string1, string2);
cout<<"\nSetelah digabung, string1 sekarang menjadi:
"<<string1<<endl;
getche(); }
5
Hasil Tampilan dari Program diatas sebagai berikut :
3) Strcmp
Digunakan untuk membandingkan 2 nilai string.
Contoh dalam penggalan program c++:
#include <iostream.h>
#include <stdio.h>
#include <conio.h>
main()
{
char sa[]="Logika";
char sb[]="Logika Algoritma";
char sc[]="Logika Algoritma & Pemprograman";
/*Melakukan perbandingan terhadap dua string dan penampilan
nilainya*/
printf("Nilai Yang dibandingkan sa,sb : %d\n",strcmp(sa,sb));
printf("Nilai Yang dibandingkan sa,sc : %d\n",strcmp(sa,sc));
printf("Nilai Yang dibandingkan sb,sa : %d\n",strcmp(sb,sa));
getch();
return 0;
}
Hasil Tampilan dari Program diatas sebagai berikut :
6
4) Strlen
Digunakan untuk mengetahui panjang nilai string.
Contoh dalam penggalan program c++:
#include <iostream.h>
#include <conio.h>
#include <string.h>
main()
{
char nama[50] = "Logika Algoritma";
char kosong[50] = "";
clrscr();
cout << "jumlah karakter dari nama adalah " << strlen(nama) << endl;
cout << "jumlah karakter dari kosong adalah " << strlen(kosong) <<
endl;
getch();}
Hasil Tampilan dari Program diatas sebagai berikut :
5) Strchr
Digunakan untuk mencari nilai karakter dalam string.
Contoh dalam penggalan program C++:
#include <stdio.h>
#include <conio.h>
#include <string.h>
int main(void){
char str [100]="Aisyah Zahra";
char karakter='Z';
char *hasil;
hasil=strchr(str,karakter);
printf("Hasil Peubah :%s\n",hasil);
7
printf("Karakter %c ditemukan pada indeks ke-%d",karakter,(hasil-
str));
getch();
return 0; }
Hasil Tampilan dari Program diatas sebagai berikut :
2. Struktur Data
Terdiri dari :
a. Struktur Data Sederhana
Misalnya Array dan Record
1) Array
Adalah tipe tersetruktur yang terdiri dari sejumah komponen yang
mempunyai tipe yang sama. Jenis Array dibedakan menjadi 3 jenis:
array 1 dimensi, 2 dimensi dan multidimensi
2) Record
Sebuah record merupakan koleksi satuan data yang heterogen, yakni
terdiri dari berbagai type. Satuan data sering disebut sebagai field dari
record. Field dipanggil dengan namanya masing-masing.
b. Struktur Data Majemuk
Terdiri dari :
a. Linier
8
Misalnya : Stack, Queue dan Linear Linked List.
b. Non Linier
Misalnya : Pohon (Tree), Pohon Biner (Binary Tree), Pohon Cari Biner
(Binary Search Tree), General Tree serta Graph.
1.3 Konversi Bilangan
1. Decimal adalah bilangan berbasis sepuluh yang terdiridari 0, 1, 2, 3, 4, 5, 6, 7,
8, dan 9
2. Hexadecimal adalah bilangan berbasis enam belas yang terdiri dari 0, 1, 2, 3, 4,
5, 6, 7, 8, 9, A, B, C, D, E, dan F
Tabel di bawah adalah contoh konversi bilangan Decimal, dan Hexadecimal
Contoh KONVERSI ANTAR BILANGAN
Konversi Bilangan Decimal ke Hexadecimal
Contoh 254 (10) = .......(16)
Caranya dengan membagi bilangan tersebut dengan enam belas sampai bilangan
tersebut tidak bisa lagi dibagi enam belas (kurang dari enam belas) dengan
mencatat setiap sisa pembagian.
254 : 16 = 15 sisa 14 atau E (lihat tabel di atas)
15 : 16 = sisa 15 atau F (lihat tabel di atas)
Jadi 254 (10) = FE (16) diurutkan dari sisa pembagian terakhir.
9
1.4 Array
1. Pengertian Array
Array / Larik : Struktur Data Sederhana yang dapat didefinisikan sebagai
pemesanan alokasi memory sementara pada komputer. Array dapat didefinisikan
sebagai suatu himpunan hingga elemen yang terurut dan homogen. Terurut : Dapat
diartikan bahwa elemen tersebut dapat diidentifikasi sebagai elemen pertama, elemen
kedua dan seterusnya sampai elemen ke-n. Homogen : Adalah bahwa setiap elemen
dari sebuah. Array tertentu haruslah mempunyai type data yang sama. Sebuah Array
dapat mempunyai elemen yang seluruhnya berupa integer atau character atau String
bahkan dapat pula terjadi suatu Array mempunyai elemen berupa Array.
2. Karakteristik Array
a. Mempunyai batasan dari pemesanan alokasi memory (Bersifat Statis)
b. Mempunyai Type Data Sama (Bersifat Homogen)
c. Dapat Diakses Secara Acak
Tiga hal yang harus diketahui dalam mendeklarasikan array :
a. Type data array
b. Nama variabel array
c. Subskrip / index array
3. Jenis Array (yang akan dipelajari) adalah :
a. Array Dimensi Satu (One Dimensional Array)
1) Deklarasi Array Dimensi Satu
Dapat disebut juga dengan istilah vektor yang menggambarkan data
dalam suatu urutan.
10
Deklarasi : Type_Data Nama_Variabel [index]
Misalnya : int A[5];
Penggambaran secara Logika :
Contoh :
void main()
{ int bil [5];
clrscr;
cout<<"Masukkan 5 bilangan genap : "<<endl;
for (int i = 0; i < 5; i++)
{ cout<<"Bilangan ";
cout<< i + 1 <<" : ";
cin>> bil[i];
cout<<endl;
}
cout<<endl;
cout<<"5 bilangan genap yang dimasukkan “ <<endl;
for (int i = 0; i < 5; i++)
cout<<" "<<bil[i];
getch();
}
Gambar 1.1 Tampilan Program array dimensi 1
11
2) Rumus untuk menentukan jumlah elemen dalam Array :
Π = Perkalian dari elemen sebelumnya (untuk array dimensi dua &
tiga)
Contoh :
Suatu Array A dideklarasikan sbb : int A[10]; maka jumlah elemen
Array dimensi satu tersebut adalah = 10
3) Pemetaan Array Dimensi 1
Dimana :
@A[i] : Posisi Array yg dicari
B : Posisi awal index di memory komputer
I : Subkrip atau indeks array yg dicari
L : Ukuran / Besar memory suatu type data
Contoh :
Suatu Array A dideklarasikan sebagai berikut :
int A[5]; dengan alamat awal index berada di 0011 (H) dan ukuran
memory type data integer = 2. Tentukan berapa alamat array A[3]
?
12
b. Array Dimensi Dua (Two Dimensional Array)
1) Deklarasi array Dimensi Dua
Sering digunakan dalam menterjemahkan matriks pada
pemrograman.
Deklarasi : Type_Data Nama_Variabel [Index1] [index2];
Misal : int A[3][2];
Penggambaran secara Logika :
13
2) Menentukan jumlah elemen dalam Array dimensi dua:
Π = Perkalian dari elemen sebelumnya (untuk array dimensi dua
& tiga)
Contoh :
Suatu Array X dideklarasikan sbb : int X[4][3], maka jumlah
elemen Array dimensi dua tersebut adalah : (4) * (3) = 12
Terbagi Dua cara pandang (representasi) yang berbeda :
a) Secara Kolom Per Kolom (Coloumn Major Order/CMO)
b) Secara Baris Per Baris (Row Major Order / RMO)
Keterangan :
@M[i][j] : Posisi Array yg dicari,
M[0][0] : Posisi alamat awal index
array,I : Baris
j : kolom
L : Ukuran memory type data
K : Banyaknya elemen per kolom
N : Banyaknya elemen per baris
14
Penggambaran secara logika
Misal : int M[3][2]; (Array dengan 3 Baris & 2 Kolom)
3) Pemetaan Array Dimensi Dua
Contoh Pemetaan :
Suatu Array X dideklarasikan sebagai berikut : Float X[4][3],
dengan alamat index X[0][0] berada di 0011(H) dan ukuran type
data float = 4. Tentukan berapa alamat array X[3][2] berdasarkan
cara pandang baris dan kolom ?
Gambar 1.2 Contoh Pemetaan array dimensi dua
15
Contoh Program Array Dimensi Dua :
#include<stdio.h>
#include<conio.h>
main()
{
int a[3][5];
for (int i=0;i<3;i++)
{
for (int j=0;j<5;j++)
{
printf("%x ",&a[j][i]);
}
printf("\n");
}
getch();
}
Gambar 1.3 Tampilan Program Array Dimensi Dua
16
BAB II
SISTEM BILANGAN
2.1 Konsep Dasar Sistem Bilangan
Sistem bilangan adalah suatu cara untuk mewakili besaran dari suatu item fisik.
Konsep dasar sistem bilangan dikarakteristikkan oleh basis (radix), absolute digit dan
posisi (place) value, yang dituliskan:
Basis yang digunakan sistem bilangan tergantung dari jumlah nilai bilangan
yang dipergunakan.
1. Sistem Bilangan Desimal
Sistem bilangan desimal menggunakan basis 10 (deca). Menggunakan 10
macam simbol bilangan berbentuk digit angka: 0,1,2,3,4,5,6,7,8,9. Dasar
penulisan:
Bentuk nilai desimal dapat berupa integer (bilangan bulat) dan pecahan. Dapat
ditulis dalam bentuk eksponensial yaitu ditulis dengan mantissa dan exponent.
Contoh:
17
Penulisan base/radix dituliskan setelah absolut digit, yaitu A10, atau A(D).
Dalam hal ini yang dituliskan adalah A10. Contoh nilai 435210 dan 762,1510
dapat diartikan:
2. Sistem Bilangan Biner
Sistem bilangan biner menggunakan basis 2 (binary). Menggunakan 2 macam
simbol bilangan berbentuk digit angka: 0 dan 1. Penulisan base/radix dituliskan
setelah absolut digit, yaitu A2 atau A(B). Dalam hal ini yang dituliskan adalah
A2. Dasar penulisan:
Contoh penulisan: 1001 00112
3. Sistem Bilangan Oktal
Sistem bilangan oktal menggunakan basis 8 (octal). Menggunakan 8 macam
simbol bilangan berbentuk digit angka: 0,1,2,3,4,5,6,7. Penulisan base/radix
dituliskan setelah absolut digit, yaitu A8 atau A(O). Dalam hal ini yang dituliskan
adalah A8. Dituliskan:
Contoh penulisan: 3478
18
4. Sistem Bilangan Hexadecimal
Sistem bilangan hexadesimal menggunakan basis 16 (hexa). Menggunakan 16
macam simbol bilangan berbentuk digit angka:
0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F. Penulisan base/radix dituliskan setelah
absolut digit, yaitu A16 atau A(H). Dalam hal ini yang dituliskan adalah A16.
Dituliskan:
Contoh penulisan: A7816
2.2 Satuan Data
Komputer bekerja atas dasar sistem biner berupa 0 dan 1 yang disebut bit. Bit
merupakan satuan data terkecil dalam sistem komputer. Bit-bit dapat digunakan untuk
menyusun karakter apa saja. Sebuah karakter dinyatakan dengan 8 bit atau 16 bit.
1. Byte
Byte merupakan satuan yang digunakan untuk menyatakan sebuah karakter
pada sistem ASCII atau EBCDIC. 1 Byte = 8 bit.
2. Kilobyte (KB)
Biasa digunakan untuk berkas gambar berukuran kecil. 1 Kilobyte = 1024 byte
3. Megabyte (MB)
Biasa digunakan untuk menyatakan kapasitas RAM dalam PC.
1 MB = 1024 KB = 1.048.576 byte
19
4. Gigabyte (GB)
Biasa digunakan untuk menyatakan kapasitas harddisk dalam PC.
1 GB = 1024 MB = 1.073.741.824 byte
5. Terabyte (TB)
Biasa digunakan untuk menyatakan kapasitas harddisk dalam mainframe.
1 TB = 1024 GB = 1.009.511.627.776 byte
6. Petabyte (PB)
1 PB = 1024 TB
2.3 Sistem Pengkodean
Sistem yang digunakan untuk mengkodekan karakter bermacam-macam. Data
disimpan dalam memori komputer menempati posisi 1 byte, yang menggunakan
kombinasi dari digit Biner. Komputer berbeda dalam menggunakan kode biner untuk
mewakili sebuah karakter. Ada beberapa kode yang akan dibahas, yaitu BCD,
EBCDIC, ASCII dan Unicode
1. BCD (Binary Coded Decimal)
Merupakan kode biner yang digunakan hanya untuk mewakili nilai digit
desimal saja. Sebuah karakter BCD dinyatakan dengan 4 bit Karakter yang
tersedia sebanyak 10 angka, yaitu angka 0,1,2,3,4,5,6,7,8,9. Digunakan pada
komputer generasi pertama.
20
Tabel 2.1 BCD 4 bit
2. EBCDIC (Extended Binary Coded Decimal Interchange Code)
EBCDIC dikembangkan oleh IBM, yang diterapkan pada berbagai komputer
mainframe. Sebuah karakter dinyatakan dengan 8 bit. Karakter yang tersedia
sebanyak 28 = 226 karakter. Digunakan pada komputer generasi ketiga.
Tabel 2.2 EBCDIC
3. ASCII (American Standard Code for Information Interchange)
ASCII dikembangkan oleh ANSI (American National Standard Institute).
Sebuah karakter ASCII dinyatakan dengan 8 bit. Karakter yang tersedia
21
sebanyak 226 karakter, meliputi huruf, angka, dan spesial karakter, termasuk
simbol Yunani dan karakter grafis.
Tabel 2.3 ASCII
4. Unicode
Sebuah karakter Unicode dinyatakan dengan 16 bit. Karakter yang tersedia
sebanyak 65.536 karakter, meliputi huruf, angka, dan spesial karakter, termasuk
simbol Yunani, karakter grafis, simbol Arab dan Cina.
2.4 Konversi Bilangan
1. Konversi dari Bilangan Desimal ke Biner
22
Dengan cara membagi bilangan desimal dengan 2 (basis biner) sampai tidak
bisa dibagi lagi. Kemudian sisa pembagian diurutkan dari bawah ke atas dalam
format 8 bit. Contoh nilai 8910 akan dikonversikan menjadi Biner.
2. Konversi dari Bilangan Desimal ke Oktal
Dengan cara membagi bilangan desimal dengan 8 (basis oktal) sampai tidak
bisa dibagi lagi. Cara yang digunakan sama dengan bilangan biner. Contoh nilai
14710 akan dikonversikan menjadi Oktal.
3. Konversi dari Bilangan Desimal ke Hexadesimal
Dengan cara membagi bilangan desimal dengan 16 (basis hexa) sampai tidak
bisa dibagi lagi. Cara yang digunakan sama dengan bilangan biner.
23
Contoh nilai 12310 akan dikonversikan menjadi Hexa
4. Konversi dari Bilangan Biner ke Desimal
Dengan cara mengalikan masing-masing bit biner dalam bilangan sesuai
dengan radix dan position value-nya. Contoh bit 11 01012 akan dikonversikan
menjadi Desimal.
5. Konversi dari Bilangan Biner ke Oktal
Dengan cara membagi digit biner tersebut ke dalam tiga digit dari kanan. Ketiga
digit tersebut kemudian dikonversikan menjadi decimal. Contoh bit 1010 10112
akan dikonversikan menjadi Oktal.
24
6. Konversi dari Bilangan Biner ke Hexadesimal
Dengan cara membagi digit biner tersebut ke dalam empat digit dari kanan.
Keempat digit tersebut kemudian dikonversikan menjadi decimal. Contoh bit
101010112 akan dikonversikan menjadi Hexa.
7. Konversi dari Bilangan Oktal ke Desimal
Dengan cara mengalikan masing-masing bit octal dalam bilangan sesuai dengan
radix dan position valuenya. Contoh bit 3718 akan dikonversikan menjadi
Desimal.
8. Konversi dari Bilangan Oktal ke Biner
Dengan cara mengkonversikan setiap satu digit octal menjadi tiga digit biner.
Contoh bit 718 akan dikonversikan menjadi Biner.
Maka dituliskan menjadi 718 = 0011 10012
25
9. Konversi dari Bilangan Oktal ke Hexadesimal
Konversi ini tidak dapat dilakukan secara langsung, tetapi harus dikonversikan
terlebih dahulu ke Desimal atau Biner. Contoh bit 2438 akan dikonversikan
menjadi Hexa.
Maka dituliskan menjadi 2438 = A316
10. Konversi dari Bilangan Hexadesimal ke Desimal
Dengan cara mengalikan masing-masing bit hexa dalam bilangan sesuai dengan
radix dan position valuenya. Contoh bit 8F16 akan dikonversikan menjadi
Desimal.
11. Konversi dari Bilangan Hexadesimal ke Biner
Dengan cara mengkonversikan setiap satu digit hexa menjadi empat digit biner.
Contoh bit 8F16 akan dikonversikan menjadi Biner
Maka dituliskan menjadi 8F16 = 1000 11112
26
12. Konversi dari Bilangan Hexadesimal ke Oktal
Konversi ini tidak dapat dilakukan secara langsung, tetapi harus dikonversikan
terlebih dahulu ke Desimal atau Biner sama dengan konversi dari oktal ke hexa.
Contoh bit 8F16 akan dikonversikan menjadi Oktal
Maka dituliskan menjadi 8F16 = 2178
27
BAB III
REPRESENTASI DATA
3.1 Pengertian Representasi Data
Komputer menggunakan dan memanipulasi data untuk perhitungan aritmatik,
pemrosesan data, dan operasi logik. Type data yang digunakan dalam komputer digital
diklasifikasikan:
1. Data Numerik: merepresentasikan integer, pecahan, real, dan desimal berkode
biner.
2. Data Logikal: digunakan oleh operasi seperti OR, AND, COMPLEMENT,
COMPARE dan SHIFT.
3. Data Bit Tunggal: digunakan oleh operasi seperti SET, CLEAR, dan TEST.
4. Data Alfanumerik: digunakan untuk manipulasi string oleh instruksi seperti
MOVE dan SEARCH
Berikut ini merupakan Ilustrasi Representasi Data :
Gambar 3.1 Ilustrasi Representasi Data
28
3.2 Representasi Integer
Untuk keperluan pengolahan dan penyimpanan data komputer, hanya bilangan
biner yang dapat merepresentasikan bilangan Integer direpresentasikan selain oleh nilai
bilangannya juga dengan adanya tambahan tanda (Signed Integer). Berikut ini tipe-tpe
representasi integer :
1. Representasi Sign and Magnitude
Merepresentasikan bilangan integer negative. Bit yang paling kiri
diidentifikasikan sebagai tanda (sign). Jika bit paling kiri adalah nol maka
bilangan tersebut positif. Jika bit paling kiri adalah satu maka bilangan tersebut
negative.
Contoh:
+1810 = 000100102
−1810 = 100100102
a. Penjumlahan pada Sign-Magnitude mempunyai aturan:
1) Sign tidak dijumlahkan, hanya magnitude.
2) Buang carry out dari bit yang paling kiri.
3) Jumlahkan yang sign-nya sama
4) Sign hasil = sign penambah
Contoh penjumlahan 4 bit:
29
b. Pengurangan pada Sign-Magnitude mempunyai aturan:
1) Lakukan pengurangan jika sign sama
2) Jika sign tidak sama, ubah soal ke penjumlahan
Contoh pengurangan:
Kelemahan Sign-Magnitude:
Penambahan dan pengurangan memerlukan pertimbangan baik tanda
bilangan maupun nilai relatifnya.Ada dua representasi bilangan nol, yaitu
+010 = 000000002
−010 = 100000002
2. Representasi Komplemen Satu (One’s Complement)
Komplemen pada dasarnya merubah bentuk pengurangan menjadi
pertambahan. Komplementasi bilangan biner dengan cara mengubah 1 menjadi
0 dan 0 menjadi 1. Contoh:
00110110 = 11001001
3. Representasi Komplemen Dua (Two’s Complement)
Dibentuk dengan mengambil komplemen satu dari bilangannya dan dengan
menambahkan 1 pada posisi paling kanan. Contoh desimal 49 (dalam biner)
menjadi bentuk komplemen dua:
30
3.3 Penjumlahan Biner
Penjumlahan bilangan biner dilakukan sama seperti penjumlahan bilangan-
bilangan desimal. Operasi pengurangan, perkalian dan pembagian seperti yang
dilakukan pada komputer dan kalkulator digital sesungguhnya menggunakan
penjumlahan sebagai operasi dasarnya.
Ada 4 kondisi dalam penjumlahan bilangan biner:
0 + 0 = 0
1 + 0 = 1
0 + 1 = 1
1 + 1 = 0 (carry out 1)
Maksud dari carry out, hasilnya tidak bisa memuat lebih dari 1 digit, tetapi
disimpan ke dalam kolom sebelah yang lebih tinggi nilainya (digit paling kiri yang
diabaikan).
1. Penjumlahan Biner dengan Komplemen Dua
Ada beberapa kasus yang dapat dilakukan dengan komplemen dua:
a. Kasus 1: Dua Blangan Positip
Penjumlahan dari dua bilangan positip dilakukan secara langsung.
Contoh:
31
b. Kasus 2: Blangan Positip dan Negatip yang lebih kecil
Contoh: 8 + (-4).
Caranya bilangan -4 akan diubah ke dalam bentuk komplemen dua,
sehingga biner 4 (0100) menjadi:
c. Kasus 3: Blangan Positip dan Negatip yang lebih besar
Contoh: 8 + (-11).
Caranya bilangan -11 akan diubah ke dalam bentuk komplemen dua,
sehingga biner 11 (1101) menjadi:
d. Kasus 4: Dua Blangan Negatip
Contoh: -8 + (-7)
32
Caranya bilangan -8 dan -7 akan diubah ke dalam bentuk komplemen
dua, jadi biner 8 (1000) dan 7 (0111) menjadi:
33
BAB IV
ARRAY DIMENSI BANYAK
4.1 Array Dimensi Tiga (Three Dimensional Array)
1. Deklarasi Array Dimensi Tiga
Digunakan untuk mengelola data dalam bentuk 3 dimensi atau tiga sisi.
Deklarasi : Type_Data Nama_Variabel [index1] [ndex2] [index3];
Misal : int A [3][4][2];
Gambar 4.1 Penggambaran Logika Array Dimensi Tiga
2. Menentukan jumlah elemen dalam Array dimensi 3 :
Π = Perkalian dari statemen sebelumnya
Contoh :
Suatu Array X dideklarasikan sbb : int A [3][4][2]; maka jumlah elemen Array
dimensi tiga tersebut adalah : (3) * (4) * (2) = 24
34
3. Pemetaan Array Dimensi Tiga
Contoh :
Suatu Array A dideklarasikan sebagai berikut : int A [2][4][3], dengan alamat
awal index A[0][0][0] berada di 0011(H) dan ukuran type data int = 2 Tentukan
berapa alamat array di A[2][3][2] ?
4. Contoh Program Array Dimensi Tiga
35
Gambar 4.2 Tampilan Program Array Dimensi Tiga
4.2 Tringular Array
Tringular Array dapat merupakan Upper Tringular (seluruh elemen di bawah
diagonal utama = 0), ataupun Lower Tringular (seluruh elemen di atas diagonal utama
= 0). Dalam Array Lower Tringular dengan N baris, jumlah maksimum elemen <> 0
pada baris ke-I adalah = I, karenanya total elemen <> 0, tidak lebih dari
36
Contoh :
Diketahui suatu array segitiga atas memiliki 3 baris dan kolom, tentukan
berapakah jumlah elemen yang bukan nol pada array tersebut.
I = N(N+1) / 2
I = 3 (3+1) / 2
= 12 / 2
= 6
Contoh bentuk array nya adalah seperti dibawah ini :
Suatu Array Upper Tringular dan Array Lower Tringular dapat dengan order
yang sama, dapat disimpan sebagai suatu array dengan order yang berbeda,
Contohnya :
Sparse Array
Suatu Array yang sangat banyak elemen nol-nya, contohnya adalah Array A
pada Gambar berikut :
37
BAB V
SINGLE LINKED LIST (NON CIRCULAR)
5.1 Konsep Pointer dan Linked List
Untuk mengolah data yang banyaknya tidak bisa ditentukan sebelumnya, maka
disediakan satu fasilitas yang memungkinan untuk menggunakan suatu perubah yang
disebut dengan perubah dinamis (Dinamic variable). Perubah Dinamis (Dinamic
variable) adalah suatu perubah yang akan dialokasikan hanya pada saat diperlukan,
yaitu setelah program dieksekusi. Perbedaan Perubah Statis & Dinamis adalah pada
perubah statis, isi memory pada lokasi tertentu (nilai perubah) adalah data
sesungguhnya yang akan diolah. Sedangkan pada perubah dinamis, nilai perubah
adalah alamat lokasi lain yang menyimpan data sesungguhnya. Dengan demikian data
yang sesungguhnya dapat dimasukkan secara langsung. Dalam hal cara pemasukkan
data dapat diilustrasikan seperti dibawah ini.
Gambar 5.1 Ilustrasi Peubah Dinamis dan Peubah Statis
5.2 Pointer
Pointer digunakan sebagai penunjuk ke suatu alamat memori. Dalam
pemrograman C++, Type Data Pointer dideklarasikan dengan bentuk umum : Type
Data * Nama Variabel.
38
Type Data dapat berupa sembarang type data, misalnya char, int atau float.
Sedangkan Nama variabel merupakan nama variabel pointer Contoh penggunaan
pointer dalam program C++:
Void main()
{
int x,y,*z;
x = 75; //nilai x = 75
y = x; //nilai y diambil dari nilai x
z = &x; //nilai z menunjuk kealamat pointer dari nilai
x
getch();
}
5.3 Linked List
Salah satu Struktur Data Dinamis yang paling sederhana adalah Linked List
atau Struktur Berkait atau Senarai Berantai, yaitu suatu kumpulan komponen yang
disusun secara berurutan dengan bantuan Pointer. Linked List (Senarai Berantai)
disebut juga dengan Senarai Satu Arah (One-Way List). Masing-masing
Gambar 5.2 Contoh Linked List
Berikut ini merupakan perbedaan karakteristik Array dengan Linked List :
39
Setiap simpul dalam suatu Linked List terbagi menjadi dua bagian,yaitu :
1. Medan Informasi
Berisi informasi yang akan disimpan dan diolah.
2. Medan Penyambung (Link Field)
Berisi alamat berikutnya. Bernilai 0, Jika Link tersebut tidak menunjuk ke Data
(Simpul) lainnya. Penunjuk ini disebut Penunjuk Nol.
Linked List juga mengandung sebuah variable Penunjuk List, yang biasanya
diberi nama START (AWAL) yang berisi alamat dari simpul pertama dalam
List.
Gambar 5.3 Contoh Linked List dengan Penunjuk List
Berikut ini merupakan contoh dari Penyajian Linked List Dalam Memory :
Gambar 5.4 Penyajian Linked List dalam Memory
40
5.4 Single Linked List Non Circular
1. Pengetian Single Linked List
Kata Single berarti field pointer-nya hanya satu dan satu arah,pada akhir node
pointernya menunjuk NULL.
Gambar 5.5 Menempati alamat memori tertentu
Sedangkan Linked List merupakan node-node tersebut saling terhubung satu sama lain.
Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya,
dan juga memiliki field yang berisi data. Node terakhir akan menunjuk ke NULL yang
akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list.
Gambar 5.6 Contoh Linked Linst Non Circular
2. Pembuatan Single Linked List Non Circular
Deklarasi Node :
typedef struct TNode{
41
int data;
TNode *next;
};
Keterangan:
a. Pembuatan struct bernama TNode yang berisi 2 field, yaitu field data
bertipe integer dan field next yang bertipe pointer dari TNode
b. Setelah pembuatan struct, buat variabel head yang bertipe pointer dari
TNode yang berguna sebagai kepala linked list.
c. Digunakan perintah new untuk mempersiapkan sebuah node baru berserta
alokasi memorinya, kemudian node tersebut diisi data dan pointer nextnya
ditunjuk ke NULL.
TNode *baru;
baru = new TNode;
baru->data = databaru;
baru->next = NULL;
5.5 Single Linked List Non Circular Menggunakan Head
Dibutuhkan satu buah variabel pointer : head yang akan selalu menunjuk pada
node pertama. Berikut contohnya :
Gambar 5.7 Contoh Single Linked List Non Circular Menggunakan Head
42
1. Deklarasi Pointer Penunjuk Head Single Linked List
Manipulasi linked list tidak dapat dilakukan langsung ke node yang dituju,
melainkan harus menggunakan suatu pointer penunjuk ke node pertama (Head) dalam
linked list. Deklarasinya sebagai berikut:
TNode *head;
Fungsi Inisialisasi Single Linked List
void init()
{
head = NULL;
}
2. Function untuk mengetahui kondisi Single Linked List
Jika pointer head tidak menunjuk pada suatu node maka kosong
int isEmpty()
{
if (head == NULL) return 1;
else return 0;
}
3. Menambah Node di Depan
Penambahan node baru akan dikaitan di node paling depan, namun pada saat
pertama kali (data masih kosong), maka penambahan data dilakukan dengan cara: node
head ditunjukkan ke node baru tersebut. Prinsipnya adalah mengkaitkan node baru
dengan head, kemudian head akan menunjuk pada data baru tersebut sehingga head
akan tetap selalu menjadi data terdepan.
43
Berikut contoh bagian listing untuk menambah node di depan dengan
menggunakan C++ :
Ilustrasi penambahan node didepan, sebagai berikut :
Gambar 5.8 Ilustrasi penambahan node didepan
44
4. Menambah Node di Belakang
Penambahan data dilakukan di belakang, namun pada saat pertama kali, node
langsung ditunjuk oleh head. Penambahan di belakang membutuhkan pointer bantu
untuk mengetahui node terbelakang. Kemudian, dikaitkan dengan node baru. Untuk
mengetahui data terbelakang perlu digunakan perulangan.Berikut contoh listing
penambahan node di belakang dengan menggunakan C++ :
Ilustrasi penambahan node dibelakang sebagai berikut :
Gambar 5.9 Ilustrasi penambahan node dibelakang
45
5. Menghapus Node di Depan
Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk
oleh pointer, maka harus dilakukan penggunakan suatu pointer lain (hapus) yang
digunakan untuk menunjuk node yang akan dihapus, barulah kemudian menghapus
pointer hapus dengan menggunakan perintah delete. Sebelum data terdepan dihapus,
terlebih dahulu head harus menunjuk ke node berikutnya agar list tidak putus, sehingga
node setelah head lama akan menjadi head baru. Jika head masih NULL maka berarti
data masih kosong!. Berikut contoh listing menghapus node didepan dengan
menggunakan C++ :
Ilustrasi penghapusan node didepan sebagai berikut :
Gambar 5.10 Ilustrasi penghapusan node didepan
46
6. Menghapus Node di Belakang
Membutuhkan pointer bantu dan hapus. Pointer hapus digunakan untuk
menunjuk node yang akan dihapus, pointer bantu untuk menunjuk node sebelum node
yang dihapus yang akan menjadi node terakhir. Pointer bantu digunakan untuk
menunjuk ke nilai NULL. Pointer bantu selalu bergerak sampai sebelum node yang
akan dihapus, kemudian pointer hapus diletakkan setelah pointer bantu. Selanjutnya
pointer hapus akan dihapus, pointer bantu akan menunjuk ke NULL. Berikut ini contoh
listing menghapus node di belakang dengan menggunakan C++ :
Ilustrasi penghapusan node dibelakang sebagai berikut:
Gambar 5.11 Ilustrasi penghapusan node dibelakang
47
7. Function untuk menghapus semua elemen
Berikut ini merupakan contoh listing dengan menggunakan C++ untuk
menghapus semua elemen yang berada didalam linked list:
void clear()
{
TNode *bantu,*hapus;
bantu = head;
while(bantu!=NULL)
{
hapus = bantu;
bantu = bantu->next;
delete hapus;
}
head = NULL;
}
5.6 Menampilkan Isi Linked List
Linked list ditelusuri satu-persatu dari awal sampai akhir node. Penelusuran
dilakukan dengan menggunakan pointer bantu, karena pointer head yang menjadi tanda
awal list tidak boleh berubah/berganti posisi. Penelusuran dilakukan terus sampai
ditemukan node terakhir yang menunjuk ke nilai NULL. Jika tidak NULL, maka node
bantu akan berpindah ke node selanjutnya dan membaca isi datanya dengan
menggunakan field next sehingga dapat saling berkait. Jika head masih NULL berarti
data masih kosong!. Berikut ini contoh listing dengan menggunakan C++ untuk
menampilkan isi Linked List :
void tampil(){
TNode *bantu;
bantu = head;
if(isEmpty()==0){
while(bantu!=NULL){
cout<<bantu->data<<" ";
bantu=bantu->next;
}
48
printf(“\n”);
} else printf(“Masih kosong\n“);
Gambar 5.12 Menampilkan Isi Linked List
5.7 Singled Linked List Non Circular Menggunakan Head dan Tail
Dibutuhkan dua variabel pointer : head dan tail. Head selalu menunjuk pada
node pertama, sedangkan tail selalu menunjuk pada node terakhir. Kelebihan dari
Single Linked List dengan Head & Tail adalah pada penambahan data di belakang,
hanya dibutuhkan tail yang mengikat node baru saja tanpa harus menggunakan
perulangan pointer bantu.
Gambar 5.13 Contoh Linked List dengan Head dan Tail
1. Inisialisasi Linked List
TNode *head, *tail;
2. Fungsi Inisialisasi Linked List
void init(){
head = NULL;
tail = NULL;
49
}
3. Function untuk mengetahui kondisi LinkedList kosong / tidak
int isEmpty(){
if(tail == NULL) return 1;
else return 0;
}
4. Menambah Node di Depan dengan Head dan Tail
Berikut contoh listing dengan menggunakan C++ untuk menambah Node di
depan dengan Head dan Tail :
Ilustrasi penambahan node didepan dengan head dan tail sebagai berikut :
50
Gambar 5. 14 Ilustrasi penambahan node didepan dengan head dan tail
5. Menambah Node di Belakang dengan Head dan Tail
Berikut contoh listing dengan menggunakan C++ untuk menambah Node di
belakang dengan Head dan Tail :
Ilustrasi penambahan node dibelakang dengan head dan tail sebagai berikut :
51
Gambar 5. 15 Ilustrasi penambahan node dibelakang dengan head dan tail
6. Menghapus Node di Depan (Dengan Head dan Tail)
Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk
oleh pointer, maka harus dilakukan penunjukkan terlebih dahulu dengan pointer hapus
pada head, kemudian dilakukan pergeseran head ke node berikutnya sehingga data
setelah head menjadi head baru, kemudian menghapus pointer hapus dengan
menggunakan perintah delete. Jika tail masih NULL maka berarti list masih kosong!.
Berikut contoh listing dengan menggunakan C++ untuk mengahous Node di depan
dengan Head dan Tail :
52
Ilustrasi Menghapus Node di Depan (Dengan Head dan Tail) sebagai berikut :
Gambar 5. 16 Ilustrasi menghapus node ddepan dengan head dan tail
7. Menghapus Node di Belakang (Dengan Head dan Tail)
Penghapusan node tidak boleh dilakukan jika keadaan node sedang ditunjuk
oleh pointer, maka harus dilakukan penunjukkan terlebih dahulu dengan variable hapus
pada tail. Jika tail masih NULL maka berarti list masih kosong! Dibutuhkan pointer
bantu untuk membantu pergeseran dari head ke node berikutnya sampai sebelum tail,
sehingga tail dapat ditunjukkan ke bantu, dan bantu tersebut akan menjadi tail yang
baru. Setelah itu hapus pointer hapus dengan menggunakan perintah delete. Berikut
contoh listing dengan menggunakan C++ untuk mengahpus Node di belakang dengan
Head dan Tail :
53
Ilustrasi Menghapus Node di Belakang (Dengan Head dan Tail) sebagai
berikut:
Gambar 5. 17 Ilustrasi menghapus node dibelakang dengan head dan tail
8. Function untuk menghapus semua elemen
Berikut ini merupakan contoh listing dengan menggunakan C++ untuk
menghapus semua elemen yang berada didalam linked list dengan head dan tail:
void clear()
{
TNode *bantu,*hapus;
bantu = head;
while(bantu!=NULL)
{
hapus = bantu;
bantu = bantu->next;
delete hapus;
}
head = NULL;
tail = NULL;
}
54
BAB VI
STACK ATAU TUMPUKAN
6.1 Pengertian Stack atau tumpukan
Merupakan bentuk khusus dari Linier List yang pemasukan dan penghapusan
elemennya hanya dapat dilakukan pada satu posisi, yaitu posisi akhir dari List (Top).
Prinsip Stack adalah LAST-IN-FIRST-OUT (LIFO).
6.2 Operasi Stack atau Tumpukan
1. Deklarasi Stack
Deklarasi MAX_STACK
#define MAX_STACK 5
Deklarasi STACK dengan struct dan array data
typedef struct STACK{
int top;
int data[5];
};
Deklarasi variabel stack dari struct
STACK tumpuk;
2. Inisialisasi
a. Pada mulanya isi top dengan-1, karena array dalam C/C++ dimulai dari 0,
berarti stack adalah KOSONG
55
b. TOP adalah variable penanda dalam STACK yang menunjukkan elemen
teratas Stack.
c. TOP of STACK akan selalu bergerak hingga mencapai MAX of STACK
sehingga menyebabkan stack PENUH
Gambar 6.1 Contoh Stack
3. Operasi Stack
a. ISEMPTY
Digunakan untuk memeriksa apakah stack masih dalam kondisi kosong.
Dengan cara memeriksa TOP of STACK. Jika TOP masih = -1 maka
berarti stack masih kosong.
Gambar 6.2 Contoh Isempty
56
b. ISFULL
Digunakan untuk memeriksa apakah kondisi stack sudah penuh. Dengan
cara memeriksa TOP of Stack. Jika TOP of STACK = MAX_STACK-1
maka FULL (Penuh). Jika TOP of STACK < MAX_STACK-1 maka
belum penuh
Gambar 6.3 Contoh Isfull
c. PUSH
Untuk menambahkan item pada posisi paling atas (TOP). Digunakan
untuk memasukkan elemen ke dalam stack dan selalu menjadi elemen
teratas stack. Dengan cara :
1) Menambah satu (increment) nilai TOP of STACK setiap ada
penambahan elemen stack selama stack masih belum penuh
2) Isikan nilai baru ke stack berdasarkan indeks TOP of STACK setelah
ditambah satu (diincrement)
57
Gambar 6.4 Contoh Push
d. POP
Digunakan untuk menghapus elemen yang berada pada posisi paling atas
dari stack. Dengan cara :
1) Ambil dahulu nilai elemen teratas stack dengan mengakses TOP of
STACK.
2) Tampilkan nilai yang akan diambil.
3) Lakukan decrement nilai TOP of STACK sehingga jumlah elemen
stack berkurang 1
Gambar 6.5 Contoh Pop
58
e. CLEAR
Digunakan untuk mengosongkan stack / membuat stack hampa sehingga
Top pada Stack berada kembali di posisi Top = -1
Gambar 6.6 Contoh Clear
59
BAB VII
QUEUE (ANTRIAN)
7.1 Pengertian Queue (Antrian)
Struktur Data Antrean (Queue) adalah suatu bentuk khusus dari List Linier
dengan operasi pemasukan data hanya diperbolehkan pada salah satu sisi, yang disebut
sisi Belakang / ekor (Tail) dan operasi penghapusan hanya diperbolehkan pada sisi
lainnya yang disebut sisi Depan / kepala (Head) dari LinkedList. Prinsip Antrean :
FIFO (First In First Out) atau FCFS (First Come First Serve) atau “Yang Tiba lebih
awal Maka akan dilayani Terlebih Dahulu”.
7.2 Deklarasi Queue
Gambar 7.1 Contoh Queue
60
7.3 Operasi Pada Queue
Berikut ini merupakan operasi pada queue atau antrian :
1. CREATE
Digunakan untuk membentuk dan menunjukan awal terbentuknya suatu
Antrean / Queue. Untuk menciptakan dan menginisialisasi Queue dengan cara
membuat Head dan Tail = -1.
Gambar 7.2 Contoh Membuat Queue
2. ISEMPTY
Untuk memeriksa apakah Antrian penuh atau kosong. Dengan cara memeriksa
nilai Tail, jika Tail = -1 maka antrian kosong (empty). Head adalah tanda untuk kepala
antrian (elemen pertama dalam antrian) yang tidak akan berubah-ubah. Pergerakan
pada Antrian terjadi dengan penambahan elemen Antrian kebelakang, yaitu
menggunakan nilai Tail
61
Gambar 7.3 Contoh Penggunaan Isempty
3. ISFULL
Untuk mengecek apakah Antrian sudah penuh atau belum. Dengan cara :
Mengecek nilai Tail. Jika tail = MAX-1 berarti antrian sudah penuh (MAX-1 adalah
batas elemen array dalam program C++)
Gambar 7.4 Contoh Penggunaan Isfull
4. ENQUEUE
Untuk menambahkan elemen ke dalam Antrian, penambahan elemen selalu
dilakukan pada elemen paling belakang. Penambahan elemen selalu menggerakan
variable Tail dengan cara menambahkan Tail terlebih dahulu.
62
Gambar 7.5 Contoh Penggunaan Enqueue
Berikut merupakan penggalan listing enqueue dengan menggunakan C++ :
5. DEQUEUE
Digunakan untuk menghapus elemen terdepan (head) dari Antrian. Dengan cara
: menggeser semua elemen antrian kedepan dan mengurangi Tail dgn 1. Penggeseran
dilakukan dengan menggunakan looping. Berikut merupakan penggalan listing
dequeue dengan menggunakan C++ :
63
Gambar 7.6 Contoh Penggunaan Dequeue
6. CLEAR
Untuk menghapus elemen-elemen Antrian dengan cara membuat Tail dan Head
= -1. Penghapusan elemen-elemen Antrian sebenarnya tidak menghapus arraynya,
namun hanya mengeset indeks pengaksesan-nya ke nilai -1 sehingga elemen-elemen
Antrian tidak lagi terbaca sehingga mengembalikan antrian seperti keadaan semula.
Berikut merupakan penggalan listing clear dengan menggunakan C++ :
Antrian setelah di lakukan Clear
Gambar 7.7 Contoh Penggunaan Clear
64
BAB VIII
STRUKTUR POHON & KUNJUNGAN POHON BINER
8.1 Pengertian Tree (Pohon)
Pohon (Tree) termasuk struktur non linear yang didefinisikan sebagai data yang
terorganisir dari suatu item informasi cabang yang saling terkait
8.2 Isilah Dasar dalam Pohon
Pohon atau Tree adalah salah satu bentuk Graph terhubung yang tidak
mengandung sirkuit. Karena merupakan Graph terhubung, maka pada Pohon (Tree)
selalu terdapat Path atau Jalur yang menghubungkan setiap simpul dalam dua pohon.
Pohon (Tree) dapat juga didefinisikan sebagai kumpulan elemen yang salah satu
elemennya disebut dengan Akar (Root) dan sisa elemen lain (Simpul) yang terpecah
menjadi sejumlah himpunan yang saling tidak berhubungan yang disebut dengan
Subpohon (Subtree) atau cabang
8.3 Isilah-Istilah dalam Pohon
Gambar 8.1 Contoh Pohon
65
1. Predesesor
Node yang berada diatas node tertentu. (contoh : B predesesor dari E dan F)
2. Succesor
Node yang berada dibawah node tertentu. (contoh : E dan F merupakan
succesor dari B)
3. Ancestor
Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang
sama. (contoh : A dan B merupakan ancestor dari F)
4. Descendant
Seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang
sama. (contoh : F dan B merupakan ancestor dari A)
5. Parent
Predesesor satu level diatas satu node (contoh : B merupakan parent dari F)
6. Child
Succesor satu level dibawah satu node (contoh : F merupakan child dari B)
7. Sibling
Node yang memiliki parent yang sama dengan satu node (contoh : E dan F
adalah sibling)
8. Subtree
Bagian dari tree yang berupa suatu node beserta descendant-nya (contoh :
Subtree B, E, F dan Subtree D, G, H)
66
9. Size
Banyaknya node dalam suatu tree (contoh : gambar tree diatas memiliki size =
8)
10. Height
Banyaknya tingkat/level dalam suatu tree (contoh : gambar tree diatas memiliki
height = 3)
11. Root (Akar)
Node khusus dalam tree yang tidak memiliki predesesor (Contoh : A)
12. Leaf (Daun)
Node-node dalam tree yang tidak memiliki daun (contoh : Node E,F,C,G,H)
13. Degree (Derajat)
Banyaknya child yang dimiliki oleh suatu node (contoh : Node A memiliki
derajat 3, node B memiliki derajat 2)
8.4 Sifat Utama Pohon Berakar
Pembentukan Pohon
67
1. Jika Pohon mempunyai Simpul sebanyak n, maka banyaknya ruas atau edge
adalah (n-1).
2. Mempunyai Simpul Khusus yang disebut Root, jika Simpul tersebut memiliki
derajat keluar >= 0, dan derajat masuk = 0.
3. Mempunyai Simpul yang disebut sebagai Daun / Leaf, jika Simpul tersebut
berderajat keluar = 0, dan berderajat masuk = 1.
4. Setiap Simpul mempunyai Tingkatan / Level yang dimulai dari Root yang
Levelnya = 1 sampai dengan Level ke – n pada daun paling bawah. Simpul
yang mempunyai Level sama disebut Bersaudara atau Brother atau Stribling.
5. Pohon mempunyai Ketinggian atau Kedalaman atau Height, yang merupakan
Level tertinggi
6. Pohon mempunyai Weight atau Berat atau Bobot, yang banyaknya daun (leaf)
pada Pohon.
7. Banyaknya Simpul Maksimum sampai Level N adalah :
8. Banyaknya Simpul untuk setiap Level I adalah :
Hutan (Forest) adalah kumpulan Pohon yang tidak saling berhubungan. Diketahui
suatu bentuk Pohon Berakar T sebagai berikut :
68
d. Level (tingkatan) Pohon = 4 yaitu :
Level 1 = Simpul P
Level 2 = Simpul Q dan T
Level 3 = Simpul R, S dan U
Level 4 = Simpul V dan W
e. Ketinggian atau kedalaman = jumlah level = 4
f. Weight atau berat atau bobot = jumlah daun = 4
Dalam gambar Pohon T diatas dapat dibentuk 2 buah hutan (forest), bila
simpul P dihilangkan, yaitu : Hutan 1 : Q,R,S Hutan 2 : T,U,V,W
g. Banyaknya Simpul Maksimum yang dapat terbentuk sampai Level 4 (bila
simpul pada pohon dianggap penuh) adalah :
2 (N) – 1
2 (4) – 1 = 16 – 1 = 15
Gambar 8.2 Banyak Simpul
69
h. Banyaknya Simpul maksimum untuk setiap Level I (bila simpul pada pohon
dianggap penuh) adalah :
Maksimum Simpul pada level 2 = 2 ( I – 1)
= 2 (2-1) = 2
Maksimum Simpul pada level 3 = 2 (3-1) = 4
Maksimum Simpul pada level 4 = 2 (4-1) = 2
Gambar 8.3 Banyak Simpul setiap Level
8.5 Pohon Biner (Binary Tree)
Struktur ini biasanya digunakan untuk menyajikan data yang mengandung
hubungan hirarkial antara elemenelemennya. Bentuk Pohon Berakar yang lebih mudah
dikelola dalam komputer adalah Pohon Biner (Binary Tree) yang lebih dikenal sebagai
Pohon Umum (General Tree) yang dapat didefinisikan sebagai kumpulan simpul yang
mungkin kosong atau mempunyai akar dan dua Subpohon yang saling terpisah yang
disebut dengan Subpohon Kiri / cabang kiri (Left Subtree) dan Subpohon Kanan /
cabang kanan (Right Subtree).
Karakteristik Pohon Binar (Binary Tree) :
1. Setiap Simpul paling banyak hanya memiliki dua buah anak
2. Derajat Tertinggi dari setiap Simpul adalah dua.
70
3. Dibedakan antara Cabang Kiri dan Cabang Kanan.
4. Dimungkinkan tidak mempunyai Simpul
Berikut ini diberikan contoh gambar Pohon Binar (Binary Tree) dengan
Cabang Kiri dan Cabang Kanan.
Gambar 8.4 Cabang Kiri dan Cabang Kanan
8.6 Istilah-istilah Pada Pohon Biner
1. Pohon Biner Penuh (Full Binary Tree)
Semua simpul (kecuali daun) memiliki 2 anak dan tiap cabang memiliki
panjang ruas yang sama
Gambar 8.5 Pohon Biner Penuh
2. Pohon Biner Lengkap (Complete Binary Tree)
Hampir sama dengan Pohon Biner Penuh, semua simpul (kecuali daun)
memiliki 2 anak tetapi tiap cabang memiliki panjang ruas berbeda.
71
Gambar 8.6 Pohon Biner Lengkap
3. Pohon Biner Similer
Dua pohon yang memiliki struktur yang sama tetapi informasinya berbeda.
Gambar 8.7 Pohon Biner Similer
4. Pohon Biner Ekivalent
Dua pohon yang memiliki struktur dan informasi yang sama.
Gambar 8.8 Pohon Biner Ekivalent
5. Pohon Biner Miring (Skewed Tree)
Dua pohon yang semua simpulnya mempunyai satu anak / turunan kecuali daun
Gambar 8.9 Pohon Biner Miring
72
8.7 Deklarasi Pohon Biner
Dalam setiap simpul selalu berisi dua buah Pointer untuk menunjuk ke cabang
Kiri dan cabang Kanan dan informasi yang akan disimpan dalam simpul tersebut.
Ilustrasi Pohon Biner
Gambar 8.10 Ilustrasi Pohon Biner
8.8 Penyajian Pohon Biner
Tree dapat dibuat dengan menggunakan linked list secara rekursif. Linked list
yang digunakan adalah double linked list non circular. Data yang pertama kali masuk
akan menjadi node root. Data yang lebih kecil dari data node root akan masuk dan
menempati node kiri dari node root, sedangkan jika lebih besar dari data node root,
akan masuk dan menempati node di sebelah kanan node root. Bila diberikan untai
HAKJCBL, maka proses untuk dapat membentuk pohon biner dari untai diatas adalah
:
73
1. Karakter pertama ‘H’ ditempatkan sebagai akar (root)
2. Karakter ‘A’,karena lebih kecil dari ‘H’, maka akan menempati cabang kiri.
3. Karakter ‘K’, karena lebih besar dari ‘H’, maka akan menempati cabang kanan.
4. Karakter ‘J’, lebih besar dari ‘H’ dan kecil dari ‘K’, maka menempati cabang
kiri ‘K’.
5. Karakter ‘C’,karena lebih besar dari ‘A’, maka akan menempati cabang kanan.
6. Karakter ‘B’, karena lebih kecil dari ‘C’, maka akan menempati cabang kiri.
7. Karakter ‘L’, lebih besar dari ‘K’, maka menempati cabang kiri kanan.
Sehingga terbentuk pohon biner seperti berikut :
Gambar 8.11 Contoh Penyajian Pohon
74
BAB IX
KUNJUNGAN PADA POHON BINER
9.1 Kunjungan Pada Pohon Biner
Kunjungan pada Pohon Biner merupakan salah satu operasi yang sering
dilakukan pada suatu Pohon Biner tepat satu kali (Binary Tree Traversal). Operasi
terbagi menjadi 3 bentuk, yaitu :
1. Kunjungan secara PreOrder (Depth First Order)
2. Kunjungan secara InOrder (Symetric Order)
3. Kunjungan secara PostOrder
Pada ketiga cara kunjungan diatas, kunjungan ke Cabang Kiri dilakukan
terlebih dahulu, baru kemudian kunjungan ke Cabang Kanan. Dengan orientasi
semacam ini, Ketiga kunjungan diatas disebut dengan Left To Right Oriented (LRO).
Jika kunjungan ke Cabang Kanan dilakukan lebih dahulu baru kemudian kunjungan ke
Cabang Kiri, maka Orientasi semacam ini disebut Right To Left Oriented (RLO).
9.2 Kunjungan Secara PreOrder (Depth First Order)
Mempunyai Urutan :
1. Cetak isi simpul yang dikunjungi (simpul akar)
2. Kunjungi Cabang Kiri
3. Kunjungi Cabang Kanan
Contoh :
75
Gambar 9.1 Kunjungan PreOrder
Hasil Kunjungan PreOrder diatas adalah A B D E C
Gambar 9.2 Contoh Kunjungan PreOrder
Berikut ini merupakan pengganlan listing menggunakan C++ untuk kunjungan
secara preorder :
76
9.3 Kunjungan Secara InOrder (Symetric Order)
Mempunyai Urutan sebagai berikut :
1. Kunjungi Cabang Kiri
2. Cetak isi simpul yang dikunjungi (Simpul Akar)
3. Kunjungi Cabang Kanan
Gambar 9.3 Kunjungan InOrder
Hasil Kunjungan Secara InOrder : D B E A C
Gambar 9.4 Contoh Kunjungan InOrder
Berikut ini merupakan pengganlan listing menggunakan C++ untuk kunjungan
secara inorder :
77
9.4 Kunjungan PostOrder
Mempunyai Urutan sebagai berikut :
1. Kunjungi Cabang Kiri
2. Kunjungi Cabang Kanan
3. Cetak isi simpul yang dikunjungi (Simpul Akar)
Gambar 9.5 Kunjungan PostOrder
Hasil dari Kunjungan PostOrder diatas adalah D E B C A
Gambar 9.6 Contoh Kunjungan PostOrder
Berikut ini merupakan pengganlan listing menggunakan C++ untuk kunjungan
secara postorder :
78
9.5 Kunjungan Level Order
Selain kunjungan yang dijelaskan diatas, masih ada satu macam kunjungan
masih ada satu macam kunjungan lagi yaitu kunjungan LevelOrder. Kunjungan dimulai
dari simpul yang ada pada tingkat 1 (Akar), diteruskan pada simpul di tingkat 2, tingkat
3 dan seterusnya. Secara singkat kunjungan Level Order ini dapat dijelaskan sebagai
berikut.
1. Dimulai dengan memasukkan Akar kedalam antrean.
2. Kemudian mengeluarkan Akar tersebut keluar dari antrean.
Pada saat Akar tersebut dikeluarkan dari antrean, cabang kiri dan cabang kanan
secara berturut-turut dimasukkan dalam antrean. Dengan kata lain jika suatu elemen
dikeluarkan dari antrean, maka cabang kiri dan kanan dari elemen yang baru saja
dikeluarkan dimasukkan kedalam antrean.
9.6 Aplikasi Pohon Biner
NOTASI PREFIX, INFIX DAN POSTFIX
Pada bagian ini akan dibahas tentang bagaimana menyusun sebuah Pohon Binar
yang apabila dikunjungi secara PreOrder akan menghasilkan Notasi Prefix, kunjungan
secara InOrder menghasilkan Notasi Infix, dan kunjungan PostOrder menghasilkan
Notasi Postfix.
79
Gambar 9.7 Contoh Aplikasi Pohon Biner
Berdasarkan Gambar diatas, apabila dilakukan kunjungan secara PreOrder, maka akan
diperoleh Notasi Prefix dari persamaan-persamaan yang digambarkan tersebut, yaitu :
+A*BC (Gambar.a)
*+AB-BC (Gambar.b)
^-*+ABC-DE+FG (Gambar.c)
Jika dilakukan kunjungan secara InOrder, akan diperoleh Notasi Infixnya, yaitu :
(A+(B*C)) (Gambar.a)
((A+B) * (B-C)) (Gambar.b)
((((A+B) * C) – (D-E))^(F+G)) (Gambar.c)
Jika dilakukan kunjungan secara PostOrder, akan diperoleh Notasi Postfixnya, yaitu :
ABC*+ (Gambar.a)
AB+BC-* (Gambar.b)
AB+C*DE--FG+^ (Gambar.c)
80
BAB X
GRAPH DAN MATRIK PENYAJIAN GRAPH
10.1 Graph
Graph merupakan salah satu dari beberapa struktur data yang paling sering
diaplikasikan dalam pemrogrman computer. Jika kita memutuskan untuk
menggunakan penyimpanan data yang bersifat eksternal, kita mungkin tidak terlalu
membutuhkan graph, tetapi untuk beberapa permasalahan dimana kita memerlukan
representasi internal dalam memori computer untuk suatu struktur data, graph tidak
bisa dihindari penggunaannya.
Secara konseptual, graph merupakan suatu struktur data yang agak berbeda
dengan pohon (tree). Dalam kenyataannya, pohon merupakan salah satu jenis graph;
pohon merupakan kasus khusus dari graph. Dalam pemrograman computer untuk
berbagai terapan, graph sering digunakan dalam berbagai cara yang relative lebih
bermanfaat dibandingkan dengan pohon. Struktur-struktur data memiliki algoritma
yang terkait pada struktur data yang bersangkutan. Sebagai contoh, pohon biner
dibentuk dengan cara seperti itu karena bentuknya memudahkan pemrograman untuk
melakukan pencarian data dan melakukan penyisipan data.
Suatu Graph mengandung 2 himpunan, yaitu :
1. Himpunan V yang elemennya disebut simpul (Vertex atau Point atau Node atau
Titik)
2. Himpunan E yang merupakan pasangan tak urut dari simpul. Anggotanya
disebut Ruas (Edge atau rusuk atau sisi).
81
Graph seperti dimaksud diatas, ditulis sebagai G(E,V).
Bnayaknya simpul (vertex) disebut Order, sedangkan banyaknya ruas (edge)
disebut Size dari Graph.
Contoh :
Gambar berikut menanyakan Graph G(E,V) dengan :
a. V mengandung 4 simpul, yaitu simpul A,B,C,D.
b. E mengandung 5 ruas, yaitu :
e1 = (A,B) e4 = (C,D)
e2 = (B,C) e5 = (B,D)
e3 = (A,D)
Gambar 10.1 Contoh Graph G(E,V)
Gambar dibawah ini menyatakan suatu Multigraph. Disini, ruas e2 pada kedua
titik ujungnya adalah simpul yang sama, yaitu simpul A. Ruas semacam ini disebut
Gelung atau Self-Loop. Sedangkan ruas e5 dan e6 mempunyai titik ujung yang sama,
yaitu simpul-simpul B dan C. Kedua ruas ini disebut ruas berganda atau ruas sejajar.
Gambar 10.2 Contoh Multigraph
82
Suatu Graph yang tidak mengandung ruas sejajar maupun self-loop, sering
disebut juga sebagai Graph sederhana atau simple Graph. Suatu Graph G’(E’,V’)
disebut Sub Graph dari G(E,V), bila E’ himpunan bagian dari E dan V’ himpunan
bagian dari V. Jika E’ mengandung semua ruas dari E yang titik ujungnya di V’, maka
G’ disebut Subgraph yang direntang oleh V’(Spanning Subgraph).
Contoh Sub Graph
Gambar 10.3 Contoh Sub Graph
Contoh Spanning Sub Graph
Gambar 10.4 Contoh Spanning Sub Graph
10.2 Graph Berlabel
Graph G disebut berlabel jika ruas dan atau simpulnya dikaitkan dengan suatu
besaran tertentu. Khususnya jika setiap Ruas e dari G dikaitkan dengan suatu bilangan
83
non negatif d(e), maka d(e) disebut bobot atau panjang dari ruas e. Contoh : Gambar
berikut ini menyajikan hubungan antar kota. Disini simpul menyatakan kota dan label
d(e) menyatakan jarak antara dua kota.
Gambar 10.5 Contoh Graph Berlabel
10.3 Derajat Graph
Derajat simpul V, ditulis d(v) adalah banyaknya ruas yang menghubungi v.
Karena setiap ruas dihitung dua kali ketika menentukan derajat suatu Graph, maka :
Jumlah derajat semua simpul suatu Graph (derajat) = dua kali banyaknya ruas Graph
(Size) Atau dapat dituliskan :
Gambar 10.6 Euler Graph
Pada gambar diatas Jumlah Semua Simpul = 4, maka Jumlah Derajat Semua
Simpul = 8. Jika Derajat masing-masing simpul pada Graph berjumlah Genap maka
Graph tersebut disebut EULER Graph
84
10.4 Multigraph
Suatu simpul disebut genap/ganjil tergantung apakah derajat simpul tersebut
genap/ganjil. Kalau terdapat self loop, maka dihitung 2 kali pada derajat simpul.
Gambar 10.7 Contoh Multigraph
Pada gambar diatas, banyak ruas/size = 7, sedangkan derajat masing-masing simpul
adalah : d(A) = 2, d(B) = 5, d(C) = 3, d(D) = 3, d(E) = 1, d(F) = 0 maka, total jumlah
derajat simpul adalah : 14. E disebut simpul bergantung/akhir, yaitu simpul yang
berderajat satu. Sedangkan F disebut simpul terpencil, yaitu simpul yang berderajat
Nol.
10.5 Keterhubungan
Walk atau perjalanan dalam Graph G adalah barisan simpul dan ruas berganti-
ganti : V1,e1,V2,e2,......., e n-1, Vn. Disini ruas ei menghubungkan simpul Vi dan
Vi+1. Banyaknya ruas disebut Panjang Walk. Walk dapat ditulis lebih singkat dengan
hanya menulis deretan ruas : e1,e2, ...., en-1 atau deretan simpul : V1, V2,....., Vn-1,
Vn dimana : V1 = simpul awal, Vn = simpul akhir. Walk disebut tertutup bila V1 =
Vn.
1. Walk disebut tertutup, yang menghubungkan V1 dan Vn, yaitu setiap ruas
menghubungkan simpul awal dan akhir.
85
Gambar 10.8 Contoh Walk tertutup
2. Trail adalah walk dengan semua ruas dalam barisan adalah berbeda
3. Path atau jalur adalah walk yang semua simpul dalam barisan adalah berbeda.
Jadi suatu path pastilah sebuah Trail.
Gambar 10.9 Contoh Graph Terbuka
Graph merupakan Walk Terbuka, karena tidak ada ruas yang menghubungkan
Simpul U dan T. Merupakan suatu Path atau Trail terbuka dengan derajat setiap
simpulnya = 2, kecuali simpul awal U dan simpul akhir T berderajat = 1.
Cycle atau sirkuit adalah suatu Trail tertutup dengan derajat setiap simpul = 2.
Cycle dengan panjang k disebut dengan k-cycle. Demikian pula jalur dengan panjang
k disebut k-jalur.
Contoh :
Gambar 10.10 Contoh Graph
86
a. Barisan ruas a,b,c,d,b,c,g,h adalah Walk bukan Trail (karena ruas b dua
kali muncul).
b. Barisan simpul A, B, E, F bukan Walk (karena tdk ada ruas yang
menghubungkan simpul B ke F).
c. Barisan simpul A, B, C, D, E, C, F adalah Trail bukan Jalur/Path (karena
c dua kali muncul)
d. Barisan ruas a, d, g, k adalah Jalur/Path karena menghubungkan A dengan
F
e. Ruas a, b, h, g, e, a, adalah Cycle.
Graph yang tidak mengandung Cycle disebut Acyclic. Contoh dari Graph
Acyclic adalah pohon atau Tree..
Gambar 10.11 Contoh SubGraph
Suatu Graph G disebut terhubung jika untuk setiap 2 simpul dari Graph
terdapat jalur yang menghubungkan 2 simpul tersebut. Subgraph yang terhubung pada
suatu Graph disebut komponen dari G bila Subgraph tersebut tidak terkandung dalam
subgraph terhubung lain yang lebih besar. Contoh :
87
10.6 Graph Terarah (Directed Graph / DiGraph)
Graph terarah adalah Graph yang dapat menghubungkan V1 ke V2 saja (1
arah). Maksimum jumlah busur dari n simpul adalah :
Suatu Graph Berarah (Directed Graph) D terdiri atas 2 himpunan :
1. Himpunan V, anggotanya disebut simpul.
2. Himpunan A, merupakan himpunan pasangan terurut, yang disebut ruas berarah
atau arkus.
Contoh, Gambar dibawah ini adalah sebuah Graph Berarah D(V,A) dengan :
1. V mengandung 4 simpul, yaitu 1, 2, 3 dan 4
2. A mengandung 7 arkus, yaitu (1,4) ,(2,1), (2,1),(4,2), (2,3), (4,3) dan (2). Arkus
(2,2) disebut gelung (self-loop), sedangkan arkus (2,1) muncul lebih dari satu
kali, disebut arkus sejajar atau arkus berganda.
Gambar 10.12 Graph Terarah
Bila arkus suatu Graph Berarah menyatakan suatu bobot, maka Graph Berarah
tersebut dinamakan jaringan / Network. Biasanya digunakan untuk menggambarkan
situasi dinamis. Bila V’ himpunan bagian dari V serta A’ himpunan bagian dari A,
dengan titik ujung anggota A’ terletak di dalam V’, maka dikatakan bahwa D’(V’,A’)
adalah Graph bagian (Subgraph) dari D(V,A). Bila A’ mengandung semua arkus
88
anggota A yang titik ujungnya anggota V’, maka dikatakan bahwa D’(V’,A’) adalah
Graph Bagian yang dibentuk atau direntang oleh V’.
10.7 Graph Tidak Terarah (Undirect Graph)
Graph Tak Terarah adalah Graph yang menghubungkan 2 Verteks V1 ke V2
dan V2 ke V1 ( 2 arah). Bila Verteks = n, maka Graph tak terarah komplit akan
mempunyai busur atau edge sama dengan : n ( n – 1 ) / 2.
Gambar 10.13 Contoh Graph Tak Terarah
10.8 Critical Path
89
10.9 Minimum Spanning Tree
Merupakan Spanning Tree yang mempunyai Bobot dan tidak mempunyai arah
dengan hasil penjumlahan bobotnya adalah minimum. Lihat gambar Graph G berikut :
Gambar 10.14 Contoh Graph
Langkah yang dilakukan untuk membentuk minimum spanning tree adalah :
Bentuk kembali semua simpul tetapi tanpa ruas. Gambar dan telusuri ruas dengan bobot
paling kecil, seterusnya (secara ascending) hingga semua simpul terhubung.
Gambar 10.15 Contoh Minimun Spanning Tree
10.10 Matriks Penyajian Graph
Misalnya disajikan Graph G dalam Matriks ruas B ukuran (M x 2), maka setiap
baris Matriks menyatakan ruas, misalnya baris (4 7) menyatakan ada ruas
menghubungkan simpul 4 dan 7. Matriks Adjacency dari Graph G, yaitu Matriks yang
menghubungkan Vertex dengan Vertex, tanpa ruas sejajar adalah Matriks A berukuran
(N x N) yang bersifat :
90
Matriks Adjacency merupakan matriks simetri. Untuk Graph dengan ruas sejajar,
Matriks Adjacency didefinisikan sebagai berikut : P, bila ada p buah ruas
menghubungkan aij = (Vi, Vj)(p>0) dan 0, bila dalam hal lain.
Matriks Incidence dari Graph G, yaitu Matriks yang menghubungkan Vertex
dengan Edge, tanpa self-loop didefinisikan sebagai Matriks M berukuran (NXM)
sebagai berikut : 1, bila ada ruas ej berujung di simpul Vi dan mij = 0, dalam hal lain.
Gambar 10.16 Matriks Adjacency
91
Gambar 10.17 Matriks Incidence
Penelusuran Graph
Dapat dilakukan dengan 2 cara, yaitu :
1. Depth First Search (DFS)
Penelusuran dengan DFS pada Graph Tak Berarah dengan melakukan
pengecekan pada Node dengan kedalaman pertama dari Node yang ditinjau.
Gambar 10.18 DFS
92
2. Beradth First Search (BFS)
Berbeda dengan cara BFS, dengan BFS penelusuran akan diawasi dari Node-1,
kemudian melebar pada Adjacent Node dari Node-1 dan diteruskan pada Node-2,
Node- 3 dan seterusnya.
Gambar 10.19 BFS
93
DAFTAR PUSTAKA
Frieyadie. 2006. Panduan Pemrograman C++. Andi : Yogyakarta
Kadir, Abdul. 2003. Pemrograman C++. Andi : Yogyakarta.
Kristanto, Andri. 2003. Struktur Data Dengan C++. Penerbit Graha Ilmu. Yogyakarta
Nugroho, Adi. 2009. Algoritma Dan Struktur Data Dalam Bahasa Java. Andi :
Yogyakarta
Sjukani. Moh. 2009. Struktur Data (Algoritma & struktur Data 2) Dengan C, C++.
Edisi 3. Mitra Wacana Media : Jakarta.