24. current->next = NULL; 25. tail = current; 26. } 27. } 5.4 Latihan 1. Buatlah algoritma untuk mencetak seluruh isi node yang terdapat pada sebuah single linked list. 2. Buatlah algoritma untuk mencari suatu nilai didalam node – node dari sebuah single linked list. 3. Jelaskan langkah untuk mengaitkan simpul baru ke ujung double linked list. 4. jelaskan langkah untuk mengaitkan simpul baru ke awal double linked list. Struktur Data dan Algoritma 46
Modul 6 STACK (Tumpukan) 6.1 STACK STACK atau Tumpukan merupakan struktur data yang memiliki proses penginputan data dengan cara menumpukan data diatas data lainnya yang menggunakan konsep First In Last Out (FILO) yaitu data yang pertama kali dimasukan akan menjadi data yang terakhir keluar, sedangkan data yang terakhir masuk akan pertama kali keluar. Stack dapat digambarkan seperti kumpulan mangkok yang ditarok di rak mangkok disebuah restorant, ketika pelayan ingin menyusun mangkok maka dia akan meletakan mangkok diatas mangkok yang lainnya sehingga akan berbentuk seperti tumpukan mangkok. Ketika mangkok akan digunakan kembali maka pelayan akan mengambil mangkok dari posisi paling atas tumpukan, jika pelayan mengambil mangkok dengan cara yang berbeda maka tumpukan mangkok akan berantakan. Gambar 6.1 Proses input Pada Gambar 6.1, menjelaskan sebuah proses penginputan dan pengambilan data pada stack yang menggunakan konsep First In Last Out (FILO). Data 1, 2, 3, dan 4 dimasukan kedalam stack yang disebut dengan operasi PUSH sedangkan untuk mengambil data 4 dari stack menggunakan operasi POP. TOP berfungsi untuk menunjukan data yang berada paling atas pada sebuah stack. Stack dibuat menggunakan array dan sebuah variable bertipe integer yang berguna untuk menunjukan posisi puncak pada stack. Pada bab ini akan menjelaskan proses implementasi stack Struktur Data dan Algoritma 47
dalam bentuk potongan-potangan kode program. Untuk membuat stack yang pertama kali dilakukan adalah deklarasi stack. Contoh 6.1 merupakan proses deklarasi stack. 1. const int ukuran =5; 2. struct stack 3. { 4. int top; 5. int tmp[ukuran]; 6. }stack; Variable const int ukuran berfungsi untuk menunjukan ukuran dari tumpukan yang akan dibuat, variable int top berfungsi untuk menyatakan kondisi tumpukan jika berisi atau tidak dan variable int tmp[ukuran] berfungsi untuk menyimpan elemen tumpukan. Selanjutnya, akan dibahas tentang fungsi-fungsi yang digunakan pada stack. 1. Fungsi createStack() Fungsi createStack() berfungsi untuk membuat sebuat stack kosong dengan posisi TOP adalah -1. Kode program berikut menunjukan cara membuat fungsi createStack. 1. void createStack() 2. { 3. stack.top=-1; 4. } 2. Fungsi isEmpty() dan isFull() Fungsi isEmpty() digunakan untuk menunjukan stack dalam keadaan kosong. Fungsi isEmpty akan mengembalikan nilai 1 ketika stack dalam keadaan kosong dan memberikan nilai balik 0 ketika stack sudah terisi. Kode program berikut menunjukan fungsi isEmpty(). 1. int isEmpty() 2. { 3. if(stack.top == -1) 4. { 5. return 1; 6. } 7. else 8. { 9. return 0; 10. } 11. } Struktur Data dan Algoritma 48
Fungsi isFull() digunakan untuk menunjukan stack dalam keadaan penuh. perintah if(stack.top == ukuran-1) akan mengembalikan nilai 1 ketika stack dalam keadaan penuh dan mengembalikan nilai 0 ketika stack belum penuh sehingga stack masih dapat diisi dengan data. Kode program berikut menunjukan fungsi isFull(). 1. int isFull() 2. { 3. if(stack.top == ukuran-1) 4. { 5. return 1; 6. } 7. else 8. { 9. return 0; 10. } 11. } 3. Fungsi Push (int data) Fungsi Push (int data) digunakan untuk menambakan elemen kedalam stack dengan menggunakan konsep First In Last Out (FILO). Jika stack sudah terisi penuh dengan kondisi TOP = Ukuran maka program akan memberikan pesan bahwa tidak dapat menambahkan elemen kedalam stack. 1. void push(int data) 2. { 3. if (isFull() == 0) 4. { 5. stack.top++; 6. stack.tmp[stack.top]= data; 7. cout << \" data \" << stack.tmp[stack.top] << \" sudah masuk da lam stack\"; 8. } 9. else{ 10. cout << \"maaf, tumpukan sudah penuh\"<< endl; 11. } 12. } Dalam fungsi push terdapat pemeriksaan, bila nilai top sama dengan atau lebih dari ukuran bearti tumpukan sudah terisi penuh. Sedangkan, jika tumpukan belum penuh maka program akan menginputkan nilai int data ke dalam tumpukan, menaikan posisi Struktur Data dan Algoritma 49
TOP ke atas stack.top++ dan menyisipkan elemen baru dari nilai int data ke posisi TOP yang baru stack.tmp[stack.top]= data. 4. Fungsi Pop () Fungsi Pop () digunakan untuk mengambil atau mengeluarkan elemen paling atas pada tumpukan dengan menggunakan konsep konsep First In Last Out (FILO) yaitu data yang paling terakhir dimasukan akan menjadi data yang paling awal diambil. Kode program berikut menunjukan fungsi pop. 1. void pop(){ 2. if(isEmpty()==0){ 3. cout << \"Data sudah dikeluarkan dari tumpukan\"<< endl; 4. stack.top--; 5. } 6. else{ 7. cout << \"Maaf, data tumpukan kosong\"<< endl; 8. } 9. } Pada program diatas terdapat pemeriksaan pada tumpukan, jika tumpukan berisi maka data yang terletak pada posisi paling atas akan dikeluarkan dan program akan menjalankan perintah untuk menurunkan posisi TOP ke bawah dengan menjalankan perintah stack.top--. Sedangkan, jika tumpukan dalam kondisi kosong dengan nilai TOP sama dengan atau kurang dari 0 maka tidak ada penghapusan elemen. 5. Fungsi Tampilkan() Fungsi tampilkan() berguna untuk menampilkan isi dari tumpukan. Jika tumpukan dalam kondisi berisi maka isi tumpukan akan di tampilkan dengan proses perulangan dilakukan mulai dari nilai yang terakhir di masukan dan jika tumpukan dalam keadaan kosong maka program akan mengeluarkan pesan tumpukan kosong. Kode program berikut menunjukan fungsi untuk menampikan isi tumpukan. 1. void tampilkan(){ 2. if(isEmpty()== 0){ 3. for (int i = stack.top; i>=0; i--){ Struktur Data dan Algoritma 50
4. cout << stack.tmp[i] << \" \"; 5. } 6. cout << endl; 7. } 8. else{ 9. cout << \"tumpukan dalam stack kosong\"<< endl; 10. } 11. } Fungsi – fungsi stack sudah dijabarkan maka langkah berikutnya adalah memanggil fungsi stack ke dalam fungsi main() yang merupakan fungsi utama untuk memanggil fungsi push, pop dan tampilkan. Kode program berikut menunjukan fungsi main(). 1. int main() = \"; 2. { 3. int menu, data; 4. createStack(); 5. do{ 6. cout << \"=======Belajar Stack========\"<<endl; 7. cout << \"1. Push \" << endl; 8. cout << \"2. Pop \" << endl; 9. cout << \"3. Tampilkan \" << endl; 10. cout << \"4. Keluar \" << endl; 11. cout << \"masukan pilikan \\t\\t = \"; 12. cin >> menu; 13. 14. switch(menu){ 15. case 1: 16. cout << \"masukan data yang akan ditambahkan ke stack 17. cin >> data; 18. push(data); 19. break; 20. case 2: 21. pop(); 22. break; 23. case 3: 24. tampilkan(); 25. break; 26. case 4: 27. cout << \"tekan enter untuk keluar\"<< endl; 28. } 29. } 30. while(menu!=4); 31. } Struktur Data dan Algoritma 51
Hasil Running Program : 6.2 Latihan 1. Tuliskan alur logika dari program diatas. 2. Modifikasi program diatas sehingga bisa memasukan ukuran stack secara manual. 3. Buatlah program untuk mencari nilai yang berada dalam stack. 4. Buatlah program untuk membalikan kalimat dengan menggunakan fungsi push dan pop pada suatu tumpukan. Struktur Data dan Algoritma 52
Modul 7 Queue (Antrean) 7.1 Queue Queue atau antrean merupakan struktur data yang memiliki proses penambahan elemen melalui bagian belakang dari sebuah antrean, sedangkan pengambilan elemen melalui bagian depan antrian. Antrean menggunakan konsep First In First Out (FIFO) yaitu elemen yang pertama kali masuk akan menjadi elemen yang pertama kali keluar dan elemen yang terakhir masuk akan menjadi elemen yang terakhir keluar. Antrean dapat digambarkan seperti antrian berobat di rumah sakit, dimana pasien yang datang paling awal untuk antrian berobat akan dilayani oleh petugas paling pertama dan pasien yang datang paling terakhir akan dilayani paling terakhir oleh petugas. Pasien tidak bisa menerobos antrian karena rumah sakit sudah memiliki prosedur antrian. Pada gambar 7.1, menunjukan proses keluar dan masuknya elemen pada antrean yang menggunakan konsep FIFO. Antrean diatas berisi 6 (enam) elemen yaitu A,B,C,D,E dan F. Elemen A merupakan data yang pertama kali masuk ke antrean sehingga terletak dibagian depan, sedangkan Elemen F merupakan data yang terakhir masuk sehingga terletak dibagian belakang antrian. Jika ada elemen G yang akan masuk ke antrian maka akan terletak di sebelah kiri elemen Struktur Data dan Algoritma 53
F atau dibelakang elemen F. Jika menghapus elemen pada antrean maka yang pertama dihapus adalah elemen A sehingga menyebabkan semua elemen akan bergeser maju dimana elemen B akan menggantikan posisi elemen A dan seterusnya. Ketika antrean sudah penuh maka tidak bisa memasukan elemen baru sebelum ada elemen yang dihapus. 7.2 Operasi Queue/Antrean Seperti yang telah di lakukan pada bab tumpukan, antrean membutuhkan ukuran untuk menentukan jumlah elemen yang bisa masuk kedalam antrean. Antrean juga menggunakan isEmpty dan isFull untuk mengetahui apakah antrean dalam keadaan kosong atau penuh seperti yang sudah dibahas pada bab stack. Pada bab ini akan membahas penyajian antrean dalam array. Contoh 7.2 menunjukan proses deklarasi antrean 1. const int ukuran =5; 2. struct queue 3. { 4. int top; 5. string tmp[ukuran]; 6. }q; 1. Inisialisasi Inisialisasi merupakan prosedur awal untuk membuat antrean yaitu membuat antrean dalam kondisi kosong. 1. void createQueue() 2. { 3. q.top=0; 4. } 2. InQueue Insert Queue digunakan untuk menambahkan elemen baru ke dalam antrian. Proses menambahkan elemen harus memperhatian antrean dalam keadaan kosong atau sudah Struktur Data dan Algoritma 54
penuh. Jika antrean dalam keadaan penuh maka elemen baru tidak dapat ditambahkan, sebaliknya jika antrean dalam keadaan kosong atau berisi belum penuh maka elemen baru dapat ditambahkan ke dalam antrian. 1. void insertQueue(string i) 2. { 3. if (isFull() == 1) 4. { 5. cout << \"maaf, antrean sudah penuh\"<< endl; 6. 7. } 8. else{ 9. q.tmp[q.top]= i; 10. cout << \" data \" << q.tmp[q.top] << \" sudah masuk dalam stack\" << endl; 11. q.top++; 12. } 13. } 3. DeQueue Delete Queue digunakan untuk menghapus/mengeluarkan elemen yang paling depan dari antrean. Sesuai dengan konsep First In First Out (FIFO) elemen yang akan keluar/dihapus terlebih dahulu adalah elemen yang berada pada posisi paling depan. Hal ini diharuskan untuk menggeser semua elemen yang ada dalam antrean untuk menempati posisi yang kosong setelah elemen terdepan dihapus/dikeluarkan. Data yang terletak paling depan akan digantikan posisinya oleh data yang ada dibelakangnya, sehingga satu persatu elemen akan bergeser satu langkah ke depan untuk mengisi ruang kosong. 1. void deleteQueue(){ 2. if(isEmpty()==1){ 3. cout << \"Maaf, data antrean kosong\"<< endl; 4. } 5. else{ 6. string pop = q.tmp[0]; 7. int i=1; 8. cout << \"Nilai \" << pop << \"keluar antrean \" << endl; 9. 10. while(i<q.top){ 11. q.tmp[i-1]=q.tmp[i]; 12. i++; 13. } Struktur Data dan Algoritma 55
14. q.top--; 15. } 16. } Berikut keseluruahan kode program queue/antrian yang telah dijabarkan beserta hasil running program. 1. #include <iostream> 2. 3. using namespace std; 4. 5. const int ukuran =5; 6. struct queue 7. { 8. int top; 9. string tmp[ukuran]; 10. }q; 11. 12. void createQueue() 13. { 14. q.top=0; 15. } 16. 17. int isEmpty() 18. { 19. if(q.top <= 0) 20. { 21. return 1; 22. } 23. else 24. { 25. return 0; 26. } 27. } 28. 29. int isFull() 30. { 31. if(q.top >= ukuran) 32. { 33. return 1; 34. } 35. else 36. { 37. return 0; 38. } Struktur Data dan Algoritma 56
39. } 40. 41. void insertQueue(string i) 42. { 43. if (isFull() == 1) 44. { 45. cout << \"maaf, antrean sudah penuh\"<< endl; 46. 47. } 48. else{ 49. q.tmp[q.top]= i; 50. cout << \" data \" << q.tmp[q.top] << \" sudah masuk dalam antre an\" << endl; 51. q.top++; 52. } 53. } 54. 55. void deleteQueue(){ 56. if(isEmpty()==1){ 57. cout << \"Maaf, data antrean kosong\"<< endl; 58. } 59. else{ 60. string pop = q.tmp[0]; 61. int i=1; 62. cout << \"Nilai \" << pop << \"keluar antrean \" << endl; 63. 64. while(i<q.top){ 65. q.tmp[i-1]=q.tmp[i]; 66. i++; 67. } 68. q.top--; 69. } 70. } 71. 72. void tampilkan(){ 73. cout << \"isi antrean : \" << endl; 74. int i=0; 75. while (i<q.top){ 76. cout << \"antrian ke : [\" << (i+1) << \"]: \" <<q.tmp[i] << endl ; 77. i++; 78. } 79. } 80. 81. 82. int main() 83. { 84. int pilih; Struktur Data dan Algoritma 57
85. string data; 86. createQueue(); 87. do{ 88. cout << \"=======Belajar Queue========\"<<endl; 89. cout << \"1. Insert Queue \" << endl; 90. cout << \"2. Delete Queue \" << endl; 91. cout << \"3. Tampilkan \" << endl; 92. cout << \"4. Keluar \" << endl; 93. cout << \"masukan pilihan = \"; 94. cin >> pilih; 95. 96. switch(pilih){ 97. case 1: 98. cout << \"masukan data yang akan ditambahkan ke antrean = \"; 99. cin >> data; 100. insertQueue(data); 101. break; 102. case 2: 103. deleteQueue(); 104. break; 105. case 3: 106. tampilkan(); 107. break; 108. case 4: 109. cout << \"tekan enter untuk keluar\"<< endl; 110. } 111. } 112. while(pilih!=4); 113. } Struktur Data dan Algoritma 58
Hasil Running Program: 7.3 Latihan 1. Buatlah alur program dari program diatas. 2. Modifikasi program diatas sehingga bisa memasukan ukuran queue secara manual dan buatlah program untuk mencari nilai yang berada dalam antrean. 3. Buatlah prosedur untuk menyisipkan elemen dalam Priority Queue / Antrean berprioritas yang bisa terjadi diawal, ditengah atau dibelakang Antrean Struktur Data dan Algoritma 59
Modul 8 TREE 8.1 Tree Tree merupakan struktur data yang menyerupai sebuah pohon terbalik (tumbuh kebawah) yang terdiri dari gabungan node (simpul) saling terhubung. Tree dapat digambarkan seperti silsilah keluarga, dimana ada nenek dan kakek sampe ke anak cucunya. Tree menunjukan hubungan antar elemen yang besifat hierarki (satu ke banyak). Selain itu, tree berguna untuk pencarian data dan menginputkan data secara beraturan. Gambar 8.1 Tree Pada gambar 8.1 menggambarkan bentuk tree yang terdiri dari 4 level, level 1 merupakan node paling atas dalam sebuah tree yaitu node 1, level 2 adalah node yang berada dibawah level 1 yaitu node 2, 3 dan 4 dan seterusnya. Dalam hirarki juga dikenal dengan banyak istilah seperti berikut. 1. Root merupakan node yang paling atas / node akar dari hierarki tree. Node 1 adalah root dari tree Struktur Data dan Algoritma 60
2. Induk (parent) merupakan node yang mempunyai anak atau node yang mempunyai note lain dibawahnya. Node 2 adalah induk dari Node 5 3. Anak (child) merupakan node yang berada dibawah suatu node tertentu. Node 6 dan Node 7 adalah anak dari Node 3. 4. Daun (Leaf) merupakan node yang tidak memiliki anak atau node yang paling bawah dari hierarki tree. Node 8, 9, dan 10 adalah node daun. 5. Simpul dalam (internal node) merupakan node yang bukan merupakan node leaf. Node 2,3,5 dan 7 adalah internal mode 6. Sibling merupakan node yang mempunyai induk yang sama, yaitu node 6 dan 7. 7. Level merupakan tingkatan bilangan yang menunjukan hierarki node. Pada gambar diatas terdapat 4 level dalam tree. 8.2 Binary Tree (Pohon Biner) Binary Tree adalah struktur data yang hanya memiliki maksimum dua child (node anak) yaitu node anak kanan dan node anak kiri dengan artian node juga boleh mempunyai 1 anak saja. Dengan ketentuan, node anak kiri memiliki nilai lebih kecil dari pada node parent dan node anak kanan memiliki nilai lebih besar dari pada node parent. Binary Tree mempunyai beberapa istilah sebagai berikut. • Size (ukuran) adalah banyaknya node yang terdapat pada pohon biner. • Depth (kedalaman) adalah panjang jalur yang menghubungkan sebuah node sampai ke node anaknya yang paling ujung (leaf). Depth biasa juga disebut height. • Full Binary Tree (Pohon Biner Penuh) adalah pohon biner yang setiap nodenya pasti memiliki 0 (nol) atau 2 (dua) node anak. • Perfect Binary Tree (Pohon Biner Sempurna) adalah pohon biner yang semua node leafnya berada pada kedalaman yang sama dari node root. Juga disebut sebagai Complete Binary Tree (Pohon Biner Lengkap). • Almost Complete Binary Tree (Pohon Biner Hampir Lengkap) adalah pohon biner yang setiap nodenya dapat memiliki 0 node anak, atau memiliki kiri, atau jika memiliki kanan harus memiliki kiri. Tidak boleh memiliki kanan saja. Struktur Data dan Algoritma 61
• Predecesor merupakan node yang berada diatas node tertentu • Successor adalah node yang berada dibawah node tertentu. • Parent adalah predecessor satu level diatas suatu node. • Child merupakan successor satu level dibawah suatu node. • Sibling adalah node node yang memiliki parent yang sama 8.3 Implementasi Implementasi dalam pemrograman dengan asumsi awal adalah data yang hendak dimasukkan ke dalam node, bertipe data integer. Berikut merupakan langkah-langkah dari proses implementasi dalam pemrograman. 1. Deklarasi Tree Langkah pertama yang dilakukan adalah mendeklarasikan tree yang akan dibuat. Tree tersusun oleh node-node yang perlu kita deklarasikan sebagai komponen node itu sendiri. 2. Menambahkan Node Pada Tree Menambahkan node pada tree akan diinputkan secara otomatis dengan mengikuti ketentuan sebagai berikut : 2. Jika tree kosong, maka node baru yang ditambahkan akan menjadi note paling atas/root Struktur Data dan Algoritma 62
3. Jika pohon tidak kosong, maka dimulai dari node root, dan akan dilakukan proses pengecekan sebagai berikut: • Jika nilai node baru lebih kecil dari nilai node yang sedang dicek, maka lihat ke kiri node tersebut. Jika kiri node tersebut kosong (belum memiliki kiri), maka node baru menjadi kiri node yang sedang dicek. Seandainya kiri node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kiri tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan. • Jika nilai node baru lebih besar dari nilai node yang sedang dicek, maka lihat ke kanan node tersebut. Jika kanan node tersebut kosong (belum memiliki kanan), maka node baru menjadi kanan node yang sedang dicek. Seandainya kanan node sudah terisi, lakukan kembali pengecekan a dan b terhadap node kanan tersebut. Pengecekan ini dilakukan seterusnya hingga node baru dapat ditempatkan. Proses penambahan node ini diimplementasikan sebagai berikut: 1. void tambahTree(int data, int node = 1) 2. { 3. if (tree[node] == int()) 4. { 5. tree[node] = data; 6. i++; 7. } 8. else if (data < tree[node]) 9. { 10. tambahTree(data, 2 * node); 11. } 12. else if (data > tree[node]) 13. { 14. tambahTree(data, 2 * node + 1); 15. } 16. } 3. Membaca dan Menampilkan Node Pada Tree Binary Tree memiliki fungsi membaca dan menampilkan atau bisa disebut dengan kunjungan seluruh node yang terdapat pada pohon biner, yaitu Pre Order, In Order dan Post Order. Semua kunjungan diawali dengan mengunjungi akar pohon. Karena proses kunjungan ini memerlukan perulangan proses yang sama namun untuk depth (kedalaman) yang berbeda, maka ketiganya diimplementasikan dengan fungsi rekursif. Struktur Data dan Algoritma 63
a) Kunjungan Pre-Order Kunjungan pre-order dilakukan mulai dari akar pohon, dengan urutan: i. Cetak isi (data) node yang sedang dikunjungi ii. Kunjungi kiri node tersebut, • Jika kiri bukan kosong, mulai lagi dari langkah pertama, terapkan untuk kiri tersebut • Jika kiri kosong, lanjut ke langkah ketiga. iii. Kunjungi kanan node tersebut, • Jika kanan bukan kosong mulai lagi dari langkah pertama, terapkan untuk kanan tersebut • Jika kanan kosong, proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya Berikut implementasi kunjungan pre-order ke dalam pemrograman: 1. void preOrder(int node = 1) 2. { 3. int kiri = 2 * node; 4. int kanan = 2 * node + 1; 5. 6. if (isEmpty() == true) 7. { 8. cout << \"Node masih kosong\" << endl; 9. return; 10. } 11. if (tree[node] != int()) 12. { 13. cout << tree[node] << \" \"; 14. 15. if (tree[kiri] != int()) 16. preOrder(2 * node); 17. if (tree[kanan] != int()) 18. preOrder(2 * node + 1); 19. } 20. } b) Kunjungan In-Order Berikut merupakan langkah-langkah pada kunjungan in-order: i. Kunjungi kiri node tersebut, Struktur Data dan Algoritma 64
• Jika kiri bukan kosong, mulai lagi dari langkah pertama, terapkan untuk kiri tersebut • Jika kiri kosong, lanjut ke langkah kedua ii. Cetak isi (data) node yang sedang dikunjungi iii. Kunjungi kanan node tersebut, • Jika kanan bukan kosong, mulai lagi dari langkah pertama, terapkan untuk kanan tersebut • Jika kanan kosong, proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya. Berikut implementasi kunjungan in-order ke dalam pemrograman: 1. void inOrder(int node = 1) 2. { 3. int kiri = 2 * node; 4. int kanan = 2 * node + 1; 5. 6. if (isEmpty() == true) 7. { 8. cout << \"Node masih kosong\" << endl; 9. return; 10. } 11. if (tree[node] != int()) 12. { 13. if (tree[kiri] != int()) 14. { 15. inOrder(2 * node); 16. } 17. 18. cout << tree[node] << \" \"; 19. 20. if (tree[kanan] != int()) 21. { 22. inOrder(2 * node + 1); 23. } 24. } 25. } c) Kunjungan Post-Order Berikut merupakan langkah-langkah pada kunjungan post-order: i. Kunjungi kiri node tersebut, Struktur Data dan Algoritma 65
• Jika kiri bukan kosong mulai lagi dari langkah pertama, terapkan untuk kiri tersebut • Jika kiri kosong, lanjut ke langkah kedua ii. Kunjungi kanan node tersebut, • Jika kanan bukan kosong, mulai lagi dari langkah pertama, terapkan untuk kanan tersebut • Jika kanan kosong, lanjut ke langkah ketiga. iii. Cetak isi (data) node yang sedang dikunjungi. Proses untuk node ini selesai, tuntaskan proses yang sama untuk node yang dikunjungi sebelumnya. Berikut implementasi kunjungan post-order ke dalam pemrograman: 1. void postOrder(int node = 1) 2. { 3. int kiri = 2 * node; 4. int kanan = 2 * node + 1; 5. 6. if (isEmpty() == true) 7. { 8. cout << \"Node masih kosong\" << endl; 9. return; 10. } 11. 12. if (tree[node] != int()) 13. { 14. if (tree[kiri] != int()) 15. { 16. postOrder(2 * node); 17. } 18. 19. if (tree[kanan] != int()) 20. { 21. postOrder(2 * node + 1); 22. } 23. 24. cout << tree[node] << \" \"; 25. } 26. } 4. Mencari Data pada Node Tree Binary tree berfungsi untuk pencarian data dengan menjelajahi node yang ada di dalam tree. Pencarian data dimulai dengan mencari dari node root, jika data yang dicari sama dengan Struktur Data dan Algoritma 66
node root maka data ditemukan. Jika tidak sesuai dengan node root maka akan dilakukan pengecekan kembali apakah data lebih kecil dari root maka akan mencari ke kiri dan data lebih besar maka akan mencari ke kanan 1. void cariDataPadaTree(int data, int node = 1) 2. { 3. if (tree[node] == int()) 4. { 5. cout << \"Data tidak ditemukan\" << endl; 6. 7. return; 8. } 9. if (data == tree[node]) 10. { 11. cout << \"Data ditemukan pada node ke : \" << node << endl; 12. 13. return; 14. } 15. else if (data < tree[node]) 16. { 17. cariDataPadaTree(data, node * 2); 18. } 19. else if (data > tree[node]) 20. { 21. cariDataPadaTree(data, 2 * node + 1); 22. } 23. } Berikut keseluruahan kode program binary tree yang telah dijabarkan beserta hasil running program 1. #include <iostream> 2. #include <vector> 3. #include <windows.h> 4. 5. using namespace std; 6. 7. vector<int> tree; 8. int i = 0; 9. 10. bool isEmpty() 11. { 12. if (i == 0) 13. { Struktur Data dan Algoritma 67
14. return true; 68 15. } 16. else 17. { 18. return false; 19. } 20. } 21. 22. void clear() 23. { 24. i = 0; 25. tree.assign(1000000, int()); 26. } 27. 28. void tambahTree(int data, int node = 1) 29. { 30. if (tree[node] == int()) 31. { 32. tree[node] = data; 33. i++; 34. } 35. else if (data < tree[node]) 36. { 37. tambahTree(data, 2 * node); 38. } 39. else if (data > tree[node]) 40. { 41. tambahTree(data, 2 * node + 1); 42. } 43. } 44. 45. void preOrder(int node = 1) 46. { 47. int kiri = 2 * node; 48. int kanan = 2 * node + 1; 49. 50. if (isEmpty() == true) 51. { 52. cout << \"Node masih kosong\" << endl; 53. return; 54. } 55. if (tree[node] != int()) 56. { 57. cout << tree[node] << \" \"; 58. 59. if (tree[kiri] != int()) 60. preOrder(2 * node); 61. if (tree[kanan] != int()) 62. preOrder(2 * node + 1); 63. } Struktur Data dan Algoritma
64. } 65. 66. void inOrder(int node = 1) 67. { 68. int kiri = 2 * node; 69. int kanan = 2 * node + 1; 70. 71. if (isEmpty() == true) 72. { 73. cout << \"Node masih kosong\" << endl; 74. return; 75. } 76. if (tree[node] != int()) 77. { 78. if (tree[kiri] != int()) 79. { 80. inOrder(2 * node); 81. } 82. 83. cout << tree[node] << \" \"; 84. 85. if (tree[kanan] != int()) 86. { 87. inOrder(2 * node + 1); 88. } 89. } 90. } 91. 92. void postOrder(int node = 1) 93. { 94. int kiri = 2 * node; 95. int kanan = 2 * node + 1; 96. 97. if (isEmpty() == true) 98. { 99. cout << \"Node masih kosong\" << endl; 100. return; 101. } 102. 103. if (tree[node] != int()) 104. { 105. if (tree[kiri] != int()) 106. { 107. postOrder(2 * node); 108. } 109. 110. if (tree[kanan] != int()) 111. { 112. postOrder(2 * node + 1); 113. } Struktur Data dan Algoritma 69
114. 115. cout << tree[node] << \" \"; 116. } 117. } 118. 119. void cariDataPadaTree(int data, int node = 1) 120. { 121. if (tree[node] == int()) 122. { 123. cout << \"Data tidak ditemukan\" << endl; 124. 125. return; 126. } 127. if (data == tree[node]) 128. { 129. cout << \"Data ditemukan pada node ke : \" << node << endl; 130. 131. return; 132. } 133. else if (data < tree[node]) 134. { 135. cariDataPadaTree(data, node * 2); 136. } 137. else if (data > tree[node]) 138. { 139. cariDataPadaTree(data, 2 * node + 1); 140. } 141. } 142. 143. int main() 144. { 145. int data, menu; 146. tree.assign(1000000, int()); 147. 148. do 149. { 150. cout << \"menu\" << endl; 151. cout << \"1. Insert data\" << endl; 152. cout << \"2. Lihat Pre-Order\" << endl; 153. cout << \"3. Liat In-Order\" << endl; 154. cout << \"4. Liat Post-Order\" << endl; 155. cout << \"5. Lihat Jumlah Node\" << endl; 156. cout << \"6. Hapus Semua Node\" << endl; 157. cout << \"7. Cari Data\" << endl; 158. cout << \"8. Keluar\" << endl; 159. cin >> menu; 160. cout << endl; 161. 162. switch (menu) 163. { Struktur Data dan Algoritma 70
164. case 1: 165. cout << \"Masukkan Data : \" << endl; 166. cin >> data; 167. cout << endl 168. << endl; 169. 170. tambahTree(data); 171. break; 172. case 2: 173. preOrder(); 174. 175. cout << endl 176. << endl; 177. 178. break; 179. case 3: 180. 181. inOrder(); 182. 183. cout << endl 184. << endl; 185. 186. break; 187. case 4: 188. 189. postOrder(); 190. 191. cout << endl 192. << endl; 193. 194. break; 195. case 5: 196. 197. cout << i << endl 198. << endl; 199. 200. break; 201. case 6: 202. 203. clear(); 204. 205. cout << \"Data sudah terhapus\" << endl 206. << endl; 207. 208. break; 209. case 7: 210. } cout << \"Masukkan Data yang akan dicari : \"; cin >> data; cariDataPadaTree(data); break; default: cout << \"Pilihan yang anda masukkan salah\" << endl; } } while (menu != 8); Struktur Data dan Algoritma 71
Hasil Running Program: 8.4 Latihan 1. Tuliskan alur program dari contoh diatas. 2. Buatlah program untuk membuat silsilah keluarga menggunakan tree 3. Buatlah fungsi atau prosedur untuk menghapus node dalam tree 4. Buatlah fungsi atau prosedur untuk mencari parent dan child dari node dalam tree Struktur Data dan Algoritma 72
Modul 9 GRAPH 9.1 Graph Graph merupakan sebuah struktur data yang paling umum dan merupakan jenis struktur data yang paling sering diaplikasikan dalam dunia pemrograman karena graph dapat mendefinisikan hubungan yang tidak terbatas antardata yang ada. Contoh masalah yang dapat direpresentasikan dengan menggunakan graph antara lain shortest path problem (masalah path minimum), maximum flow problem (masalah aliran maksimum), minimum spanning tree (masalah pencarian rentang minimum), task network problem (masalah penjadwalan tugas jaringan), four color problem. Sebuah graph dapat didefinisikan dengan menggunakan himpunan vertex dan himpunan edge (sisi) sebagai representasi keterhubungan antarvertex. Dalam notasi matematis, graph dapat dinyatakan sebagai G = (V, E), dimana: G = Graph V = Simpul, vertex, atau sebuah node tertentu E = Edge (keterhubungan antarvertex) Penulisan hubungan antara dua vertex tertentu sebagai contoh vertex X dan vertex Y dapat ditulis dengan {X,Y}. Representasi hubungan antarvertex dapat dilakukan dengan menggunakan matriks yang disebut adjacent matrix dimana baris dan kolom dari matriks merepresentasikan vertex awal dan vertex tujuan. Struktur Data dan Algoritma 73
A B C DE A 01110 B 10101 C 11010 D 10101 E 01010 Gambar 9.1(a) Gambar 9.1(b) (b)cc Pada gambar 9.1(b) diatas menggambarkan adjacent matrix yang berkorelasi dengan graph. Graph membutuhkan matriks dengan ordo (m x n). Kolom dan baris pada matriks merupakan vertex- vertex, dua vertex pada kolom dan baris yang berhubungan diberikan nilai 1 dan nilai 0 untuk menunjukan kedua vertex tidak terhubung. Gambar 9.2 Vertex Dari gambar 9.2 vertex di atas, terdapat beberapa istilah yang biasa digunakan dalam graph, yaitu: 1. Vertex Merupakan himpunan node atau titik pada sebuah graph, contoh vertex V1, V2, dan sebagainya. Struktur Data dan Algoritma 74
2. Edge Merupakan himpunan garis atau lintasan yang menghubungkan tiap vertex pada sebuah graph, contoh e1, e2, e3, dan sebagainya 3. Adjacent Merupakan sebutan untuk dua buah titik yang saling terhubung dengan satu garis (sisi), contoh vertex V2 adjacent dengan vertex V1 dan V3, tetapi tidak adjacent dengan vertex V4 4. Cycle Merupakan lintasan yang berawal dan berakhir pada simpul atau node yang sama, contoh vertex V1 berarah menuju ke vertex itu sendiri 5. Weight Merupakan bobot nilai yang dimiliki oleh sebuah lintasan (edge) antara dua buah vertex yang terhubung, namun ini hanya berlaku bagi graph yang memiliki nilai bobot saja 9.2 Graph Tidak Berarah dan Tidak Berbobot Merupakan salah satu jenis graph yang tidak memiliki nilai dan arah pada setiap lintasannya. Dimana graph ini tidak memiliki informasi awal yang digunakan dalam proses pencariannya. Graph tidak beararah dan tidak berbobot dapat di implementasikan dengan algoritma Depth First Search(DFS). Algoritma DFS merupakan algoritma pencarian yang dimulai dari sebuah vertex dalam setiap level dari yang paling kiri sampai vertex yang paling dalam, jika pada level yang paling dalam belum ditemukan solusi, maka pencarian dilanjutkan pada vertex yang sebelah kanan. Berikut merupakan ilustrasi penggunaan algoritma DFS untuk kasus blind search: (a) (b) Gambar 9.3 Algoritma DFS pada kasus blind search 75 Struktur Data dan Algoritma
(c) (d) Gambar 9.4 Algoritma DFS pencarian Vertex Pada Gambar diatas, menunjukan proses algoritma DFS. Algoritma DFS akan melakukan pencarian dari vertex yang paling kiri pada setiap levelnya yaitu dimulai dari vertex A dan dilanjutkan ke vertex B, D dan H. Selanjutnya, DFS akan mencari apakah vertex H mempunyai tetangga, kalau ada DFS akan terlebih dulu masuk ke vertex tetangga dari H yaitu vertex I setelah tidak ada lagi vertex tetangga H maka akan dilanjutkan pencarian ke atas, dan diperiksa apakah vertex D mempunyai tetangga, jika ada maka akan masuk ke vertex tetangga D yaitu vertex E. algoritma DFS akan melakukan pencarian sampai vertex dipaling kanan yaitu vertex K. 9.2.1 Implementasi Untuk mengimplementasikan algoritma DFS ke dalam pemrograman agar menghasilkan output seperti ilustrasi di atas, kita buat menjadi beberapa fungsi, yaitu 1. Fungsi Menambahkan Vertex Method ini berfungsi untuk membuat vertex baru dan mengkondisikan semua vertex ke dalam keadaan awal (belum ditelusuri), bersifat public agar dapat digunakan di fungsi main() 1. void tambahkanVertex() 2. { 3. for(i=0;i<V;i++) 4. { 5. for(j=0;j<V;j++) 6. G[i][j]=0; 7. } 8. } 2. Fungsi Menambahkan Edge Method ini berfungsi untuk membuat edge baru yang akan menghubungkan vertex-vertex yang ada berdasarkan indeksnya karena graph yang dibuat adalah jenis graph tidak berarah (undirected) maka vertex asal maupun vertex tujuan dibuat sama. Struktur Data dan Algoritma 76
1. void tambahkanEdge() 2. { 3. for(i=0;i<E;i++) 4. { 5. printf(\"Masukan edges (format: Vertex1 Vertex2) : \"); 6. scanf(\"%d%d\",&v1,&v2); 7. G[v1-1][v2-1]=1; 8. 9. } 10. } 3. Fungsi Menampilkan Vertex Method ini berfungsi untuk menampilkan vertex dari hasil penelusuran algoritma DFS yang dibuat. 1. void tampilkanVertex() 2. { 3. for(i=0;i<V;i++) 4. { 5. for(j=0;j<V;j++) 6. printf(\" %d \",G[i][j]); 7. printf(\"\\n\"); 8. } 9. } 4. Fungsi Pencarian DFS Method ini berfungsi untuk melakukan penelusuran terhadap seluruh vertex yang berdekatan (adjacent) dengannya. 1. void DFS(int i) 2. { 3. int j; 4. visited[i]=1; 5. printf(\" %d->\",i+1); 6. for(j=0;j<V;j++) 7. { 8. if(G[i][j]==1&&visited[j]==0) 9. DFS(j); 10. } 11. } Struktur Data dan Algoritma 77
5. Fungsi main() Merupakan method yang berfungsi untuk memanggil semua method yang telah dibuat sebelumnya dan merupakan fungsi utama dari program. Pertama fungsi main() akan memanggil fungsi menambahkan vertex, setelah itu fungsi selanjutnya adalah menambahkan edge, kemudian fungsi DFS dipanggil untuk memproses algoritma pencarian. Berikut merupakan baris program lengkap untuk menerapkan algoritma DFS pada graph: 1. #include <stdio.h> 2. #include <stdlib.h> 3. 4. int source,V,E,time,visited[20],G[20][20]; 5. int i,j,v1,v2; 6. 7. void DFS(int i) 8. { 9. int j; 10. visited[i]=1; 11. printf(\" %d->\",i+1); 12. for(j=0;j<V;j++) 13. { 14. if(G[i][j]==1&&visited[j]==0) 15. DFS(j); 16. } 17. } 18. 19. void tambahkanVertex() 20. { 21. for(i=0;i<V;i++) 22. { 23. for(j=0;j<V;j++) 24. G[i][j]=0; 25. } 26. } 27. 28. void tambahkanEdge() 29. { 30. for(i=0;i<E;i++) 31. { 32. printf(\"Masukan edges (format: Vertex1 Vertex2) : \" ); 33. scanf(\"%d%d\",&v1,&v2); 34. G[v1-1][v2-1]=1; 35. 36. } 37. } 38. Struktur Data dan Algoritma 78
39. void tampilkanVertex() 40. { 41. for(i=0;i<V;i++) 42. { 43. for(j=0;j<V;j++) 44. printf(\" %d \",G[i][j]); 45. printf(\"\\n\"); 46. } 47. } 48. 49. int main() 50. { 51. 52. printf(\"Contoh Program DFS pada Graphs\\n\\n\"); 53. printf(\"Masukan jumlah edges:\"); 54. scanf(\"%d\",&E); 55. printf(\"Masukan jumlah vertices:\"); 56. scanf(\"%d\",&V); 57. tambahkanVertex(); 58. tambahkanEdge(); 59. tampilkanVertex(); 60. 61. printf(\"Masukan root dari graph: \"); 62. scanf(\"%d\",&source); 63. DFS(source-1); 64. return 0; 65. } Struktur Data dan Algoritma 79
Berikut contoh kasus graph yang dapat diselesaikan dengan menggunakan metode depth first search (DFS): Gambar 9.5 Kasus menggunakan Algoritma DFS Untuk menyelesaikan contoh kasus di atas, coba running program yang sebelumnya telah dibuat, kemudian inputkan data berikut: Edge = 11 Vertex = 12 Hubungkan Edge : 12 13 24 25 36 37 48 49 5 10 6 11 7 12 Root graph = 1 Struktur Data dan Algoritma 80
Berikut hasil running dari program di atas: Dari hasil running program diatas, dapat dilihat bahwa seluruh vertex telah ditelusuri mulai dari vertex 1 sampai dengan vertex 12 sesuai dengan penelusuran pada contoh kasus graph di atas. 9.3 Graph Tidak Berarah dan Berbobot Merupakan salah satu jenis graph yang tidak memiliki arah pada setiap lintasannya, namun memiliki bobot. Artinya, meskipun tidak memiliki arah pada vertex nya (asal ke tujuan = tujuan ke asal), namun graph ini memiliki nilai bobot tertentu pada setiap lintasannya. Berikut ilustrasinya : Struktur Data dan Algoritma 81
Gambar 9.6 Penggunaan bobot pada graph Pada gambar 9.6 di atas, dapat digambarkan bahwa graph memiliki nilai bobot untuk setiap lintasannya tapi tidak beararah. Konsep dari graph tidak berarah dan berbobot biasanya digunakan untuk pencarian nilai Minimum Spanning Tree (MST), yaitu teknik yang digunakan untuk mencari biaya terkecil dalam pemasangan jaringan kabel listrik atau telepon pada suatu lokasi ke lokasi lainnya. Algoritma yang digunakan dalam graph ini adalah algoritma Kruskal. Algoritma Kruskal merupakan teknik untuk mencari nilai MST dengan cara mengambil beberapa lintasan dimulai dari nilai bobot lintasan yang paling kecil. Jika terdapat lintasan yang membentuk looping maka akan diabaikan. 9.3.1 Implementasi Gambar 9.7 Implementasi graph tidak berarah Struktur Data dan Algoritma 82
Gambar 9.7 di atas merupakan contoh kasus graph tidak berarah dan berbobot yang dapat diselesaikan dengan menggunakan algoritma Kruskal agar dapat diketahui nilai minimum spanning tree (MST). 9.4 Graph Berarah dan Berbobot Graph bearah dan berbobot mempunyai perbedaan dengan 2(dua) graph sebelumnya, graph berarah dan berbobot merupakan graph yang mempunyai arah dan bobot pada setiap lintasannya. Graph berarah dan berbobot dapat digunakan untuk pencarian lintasan terpendek dari suatu titik lokasi ke titik lokasi lainnya. Algoritma yang digunakan dalam graph ini adalah algoritma djikstra. Algoritma djikstra menggunakan strategi algoritma greedy dimana pada setiap langkah dipilih lintasan dengan bobot terkecil yang menghubungkan vertex yang sudah diambil dengan vertex yang belum diambil. Gambar 9.8 Relasi antar vertex Pada gambar di atas dapat dilihat bahwa ketika sebuah vertex awal telah ditentukan maka selanjutnya akan mencari vertex lain yang terdekat dengannya yang memiliki bobot minimum. Algoritma djikstra akan memberikan sebuah parameter nilai pada setiap vertex untuk menentukan jalur tercepatnya. Struktur Data dan Algoritma 83
9.5 Latihan 1. Buatlah program untuk menyelesaikan implementasi graph tidak berarah dan berbobot 2. Buatlah program untuk mencari jalur tercepat dari lokasi A ke lokasi B (buat gambar graphnya) menggunakan algoritma djikstra Struktur Data dan Algoritma 84
DAFTAR PUSTAKA Allen, W.M., 2007. Data structures and algorithm analysis in C++. Pearson Education India. C and C++, Pointers — Structures, Stephen Clark, University of Cambridge Introduction to C++, Massachusetts Institute of Technology Pang, B. and Lee, L., 2008. Opinion mining and sentiment analysis. Foundations and Trends® in Information Retrieval, 2(1–2), pp.1-135. Munir, R., 2011. Algoritma dan Pemrograman dalam bahasa Pascal dan C. Informatika, Bandung. Ramdhano, C., Algoritma Pemrograman dan Struktur Data menggunakan C++, Penerbit Andi., 2019. 85
Search
