Materi Tree Dan Graph Algoritma Dan Pemrograman

TREE

Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul atau node dengan satu elemen khusus yang disebut Root dan node lainnya. Tree juga adalah suatu graph yang acyclic, simple, connected yang tidak mengandung loop.

Sebuah binary search tree (BST) adalah sebuah pohon biner yang boleh kosong, dan setiap nodenya harus memiliki identifier atau value. Value pada semua node subpohon sebelah kiiri adalah selalu lebih kecil dari value dari root, sedangkan value subpohon di sebelah kanan adalah sama atau lebih besar dari value pada root, masing-masing subpohon tersebut (kiri dan kanan) itu sendiri adalah juga binary search tree.

Struktur data bst sangat penting dalam struktur pencarian, misalkan dalam kasus pencarian dalam sebuah list, jika list sudah dalam keadaan terurut maka proses pencarian akan semakin cepat, jika kita menggunakan list contigue dan melakukan pencarian biner,akan tetapi jika kita ingin melakukan perubahan isi list (insert atau delete), menggunakan list contigue akan sangat lambat, karena prose insert dan delete dalam list contigue butuh memindahkan linked-list, yang untuk operasi insert atau delete tinggal mengatur- atur pointer,akan tetapi pada n-linked list, kita tidak bisa melakukan pointer sembarangan setiap saat, kecuali hanya satu kali dengan kata lain hanya secara squential.

Pengertian Binary Tree

Binary Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkanhubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya (disebut subtree).

Dalam tree terdapat jenis-jenis tree yang memiliki sifat khusus, diantaranya adalah binary tree.

Binary tree adalah suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary treee boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya dinamakan kiri dan kanan.

Binary Tree merupakan himpunan vertex-vertex yang terdiri dari 2 subtree (dengan disjoint) yaitu subtree kiri dan subtree kanan. Setiap vertex dalam binary tree mempunyai derajat keluar max = 2.

Sebuah pohon biner adalah grafik asiklis yang terhubung dimana setiap tingkatan dari susut tidak lebih dari 3. Ini dapat ditunjukkan bahwa dalam pohon biner manapun, terdapat persis dua atau lebih simpul dengan tingkat satu daripada yang terdapat dengan tingkat tiga, tetapi bisa terdapat angka apa saja dari simpul dengan tingkat dua. Sebuah pohon biner berakar merupakan sebuah grafik yang mempunyai satu dari sudutnya dengan tingkat tidak lebih dari dua sebagai akar.

Dengan akar yang dipilih, setiap sudut akan memiliki ayah khusus, dan diatas dua anak bagaimanapun juga, sejauh ini terdapat keterbatasan informasi untuk membedakan antara anak kiri atau kanan. Jika kita membuang keperluan yang tak terkoneksi, membolehkan bermacam koneksi dalam komponen di grafik, kita memanggil struktur sebuah hutan.

Sebuah jalan lain untuk mendefinisikan pohon biner melalui definisi rekursif pada grafik langsung. Sebuah pohon biner dapat berarti:

1. Sebuah sudut tunggal.

2. Sebuah graf yang dibentuk dengan mengambil dua pohon biner, menambahkan sebuah sudut, dan menambahkan sebuah panah langsung dari sudut yang baru ke akar dari setiap pohon biner.

Istilah-istilah Dalam Pohon

Predesesor
Node yang berada diatas node tertentu. (contoh: B predesesor dari E dan F)
Succesor
Node yang berada dibawah node tertentu. (contoh: E dan F merupakan succesor dari B)
Ancestor
Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama. (contoh: A dan B merupakan ancestor dari F)
Descendant Seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama. (contoh: F dan B merupakan ancestor dari A)
Parent Predesesor satu level diatas satu node (contoh: B merupakan parent dari F)
Child Succesor satu level dibawah satu node (contoh: F merupakan child dari B)
Sibling Node yang memiliki parent yang sama dengan satu node (contoh : E dan F adalah sibling)
Subtree Bagian dari tree yang berupa suatu node beserta descendant-nya (contoh : Subtree B, E, F dan subtree D, G, H)
Size Banyaknya node dalam suatu tree (contoh: gambar tree diatas memiliki size = 8)
Heigh Banyaknya tingkat atau level dalam suatu tree (contoh: gambar tree diatas memiliki height = 3)
Root (Akar) Node khusus dalam tree yang tidak memiliki predesesor (contoh: A)
Leaf (Daun) Node-node dalam tree yang tidak memiliki daun (contoh: Node E, F, C, G, H)
Degree (Derajat) Banyaknya child yang dimiliki oleh suatu node (contoh: Node A memiliki derajat 3, node B memiliki derajat 2)

GRAPH

Graf adalah suatu diagram yang memuat informasi tertentu jika diinterpretasikan secara tepat. Dalam kehidupan sehari-hari, graf digunakan untuk menggambarkan berbagai macam struktur yang ada. Tujuannya adalah sebagai visualisasi obyek-obyek agar lebih mudah dimengerti. Beberapa contoh graf yang sering dijumpai dalam kehidupan sehari-hari antara lain: struktur organisasi, bagan alir pengambilan mata kuliah, peta, rangkaian listrik, dan lain-lain.

ALGORITMA DJIKSTRA

A. Definisi Algoritma Djikstra

Algoritma Dijkstra, (penemunya adalah seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma yang dipakai dalam memecahkan permasalahan jarak terpendek untuk sebuah graph berarah dengan bobot-bobot sisi yang bernilai positif.

B. Tujuan Algoritma Dijkstra

Tujuan Algoritma Dijkstra yaitu untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik lainnya.
Kelemahan algoritma ini adalah semakin banyak titik akan semakin memakan waktu proses.
Jumlah titik menentukan tingkat efektifitas dari algoritma djikstra.

C. Urutan Logika Algoritma Dijkstra

Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (yang belum terisi).
Set semua node “Belum terjamah” dan set node awal sebagai “Node keberangkatan”.
Dari node keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan.
Setelah selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.
Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan lanjutkan dengan kembali ke step 3.

D. Contoh Source Code

Algoritma Kruskal

A. Definisi Algoritma Kruskal

Algoritma kruskal adalah sebuah algoritma dalam teori graf yang mencari sebuah minimum spanning tree untuk sebuah graf berbobot yang terhubung. Ini berarti menemukan subset dari tepi yang membentuk sebuah pohon yang mencakup setiap titik, di mana berat total dari semua tepi di atas pohon diminimalkan.. Jika grafik tidak terhubung, maka menemukan hutan rentang minimum (pohon rentang minimum untuk setiap komponen terhubung). Algoritma Kruskal juga tergolong algoritma Greedy dalam teori graf yang digunakan untuk mencari minimum spanning tree. Algoritma ini pertama kali muncul pada tahun 1956 dalam sebuah tulisan yang ditulis oleh Joseph Kruskal. Algoritma Kruskal adalah contoh dari algoritma rakus. Algoritma ini pertama kali muncul dalam Prosiding American Mathematical Society, hal 1956.

Dasar pembentukan algoritma Kruskal berasal dari analogi growing forest. Growing forest maksudnya adalah untuk membentuk pohon merentang minimum T dari graf G adalah dengan cara mengambil satu per satu sisi dari graf G dan memasukkannya ke dalam pohon yang telah terbentuk sebelumnya. Seiring dengan berjalannya iterasi untuk setiap sisi, maka forest akan memiliki pohon yang semakin sedikit. Oleh sebab itu, maka analogi ini disebut dengan growing forest. Algoritma Kruskal akan terus menambahkan sisi – sisi ke dalam hutan yang sesuai hingga akhirnya tidak akan ada lagi forest dengan, melainkan hanyalah sebuah pohon yang merentang minimum.

Graph : kumpulan dua himpunan yaitu himpunan titik ( vertex / simpul / node ) dan kumpulan dari garis ( edge ).

Tree : graph tak berarah yang terhubung dan tidak mengandung sirkuit.

Sirkuit : simpul awal = simpul akhir.

B. Karakteristik Algoritma Kruskal

Sifat Algoritma Kruskal ini:

1. Ia bekerja tidak hanya dengan grafik diarahkan.

2. Ia bekerja dengan bobot dan tidak grafik tertimbang. Tapi, yang lebih menarik, apabila tepi yang berbobot.

3. Kruskal adalah jenis algoritma serakah yang menghasilkan solusi optimal MST.

C. Kelebihan dan Kekurangan Algoritma Kruskal

Terdapat dua macam algoritma tipe greedy yang dapat memenuhi pemecahan masalah pohon merentang ini. Yaitu algoritma Prim dan algoritma kruskal, berikut adalah kelebihan dan kekurangan algoritma Kruskal dibanding algoritma prim.

a. Kelebihan Algoritma Kruskal

Kelebihan algoritma Kruskal dibanding algoritma prim adalah sebagai berikut :

Sangat cocok diterapkan saat graf memiliki sisi berjumlah sedikit namun memiliki sangat banyak simpul, karena orientasi kerja algoritma ini adalah berdasarkan pada urutan bobot sisi, tidak berdasarkan simpul.

b. Kekurangan Algoritma Kruskal

Beberapa hal yang menjadi kekurangan algoritma kruskal dibanding algoritma prim:

Kurang cocok digunakan saat graf lengkap atau yang mendekati lengkap, dimana setiap simpul terhubungkan dengan semua simpul yang lain. Karena algoritma Kruskal menitik beratkan pada pencarian sisi, dimana sisi-sisi tersebut harus diurutkan dan ini memakan waktu yang tidak sedikit.