Graph Dan Pohon
Graph adalah sekumpulan noktah
(simpul/vertex) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan
garis (sisi/edge). Graph dapat digunakan untuk
merepresentasikan objek-objek diskrit dan hubungan antara objek-objek
tersebut. Sedangkan Pohon (tree) adalah graph yang
khusus. Pohon dapat didefinisikan sebagai graph-tak-berarah
terhubung yang tidak mengandung sirkuit (cycle).
Perbedaan antara graph dengan tree
yaitu pada graph, mampu terjadi cycle, artinya dari suatu titik
yang terhubung oleh edge dapat kembali lagi ke vertextersebut.
Sedangkan tree, merupakan suatu graf yang alur edge nya tidak
dapat kembali lagi ke vertex awalnya.
Macam – macam representasi graph dalam
struktur data:
Dengan Array yaitu pada
suatu graf, hubungan antar simpul/vertexnya direpresentasikan dengan array dua dimensi,
misalnya Array[m][n], dimana m dan n merupakan kolom dan baris yang merepresentasikan
simpul-simpulnya dan nilai dari array tersebut menandakan hubungan antar
simpul. Apakah terdapat sisi yang menghubungkan kedua simpul tersebut atau
tidak.
Contoh Graf
Array yang terbentuk :
1
|
2
|
3
|
4
|
5
|
6
|
|
1
|
1
|
1
|
0
|
0
|
1
|
0
|
2
|
1
|
0
|
1
|
0
|
1
|
0
|
3
|
0
|
1
|
0
|
1
|
0
|
0
|
4
|
0
|
0
|
1
|
0
|
1
|
1
|
5
|
1
|
1
|
0
|
1
|
0
|
0
|
6
|
0
|
0
|
0
|
1
|
0
|
0
|
Contohnya:
Pada kolom ke 1 baris 1 bernilai 1
menandakan simpul 1 dengan simpul 1 itu sendiri saling terhubung. Begitu juga
dengan kolom ke 2 baris 1 dan sebaliknya baris ke 2 kolom 1 bernilai 1 juga
menandakan adanya hubungan antara simpul 2 dengan simpul 1.
Sedangkan nilai 0 menandakan bahwa
antara kedua simpul tersebut tidak saling berhubungan.
·
Dengan Linked List yaitu node/vertex dari graf tersebut direpresentasikan
dengan linked list dari header node. Setiap dari header node tersebut berisi
dua sampai tiga field atau lebih sesuai dengan kebutuhan. Pada graf berarah dan
tak berbobot (directed-unweighted graph) minimal dibutuhka tiga field yaitu:
info, nextVtx, edgePtr. info berisi informasi tentang vertex tersebut seperti
nama vertex atau semacamnya, nextVtx adalah pointer yang menunjuk ke vertex
selanjutnya jika ada. Sedangkan edgePtr adalah pointer yang menunjuk ke edge
dari vertex tersebut. Ilustrasi Node untuk Vertex dan Edge
dengan Linked List Contoh Graf Berarah-Tak Berbobot Ilustrasi Linked List dalam
Graf Representasi graph terbaik menurut kami yaitu dengan menggunakan
linked list. Merepresentasikan graph dengan matriks adjacency seperti pada
array tidak mencukupi karena membutuhkan info lebih lanjut mengenai jumlah
node. Jika sebuah graph harus dibentuk dalam rangka pemecahan masalah, atau
harus diperbarui secara dinamik selama program berlangsung, sebuah matriks baru
harus dibuat pada setiap penambahan atau penghapusan suatu node sehingga tidak
efisien, khususnya dalam dunia nyata dimana suatu graph bisa memiliki ratusan
atau lebih node. Jadi akan lebih baik jika membuat graph menggunakan linked
list.
1.
Shortest Path Problem adalah problem bagaimana kita mencari sebuah jalur pada
graf yang meminimalkan jumlah bobot sisi pembentuk jalur tersebut.
Macam- macam algoritmanya :
a. Algoritma Dijkstra
adalah sebuah greedy algorithm dalam
memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah
simple graph takberarah (undirected graph) dengan bobot-bobot sisi (edge
weights) yang bernilai tak-negatif. Algoritma Djikstra bekerja dengan cara
mengunjungi simpul-simpul pada graf dimulai dengan simpul sumber. Kemudian
secara berulang memilih simpul-simpul terdekat dan menghitung total bobot semua
sisi yang dilewati untuk mencapai simpul tersebut. ·
Menandai simpul awal dengan [0,-] dan
statusnya permanen · Beri label untuk node yang dapat berhubungan dengan
node permanen dengan [a,b] dan status temporary dimana: a = jarak terpendek ke
node awal b = node sebelumnya/yang mendahului ·
Mencari a terkecil dan status
temporary berubah menjadi permanen · Apabila status sudah permanen semua
maka proses berhenti, tetapi apabila belum akan kembali ke langkah b.
b. Algoritma Bellman-Ford
adalah salah satu algoritma dalam
penyelesaian shortest path problem untuk weighted-directed graph (graf berarah)
dimana jika ada salah satu edge-nya yang bernilai negatif. Jika dalam graf
tersebut terdapat suatu cycle, dari edge negatif maka algoritma Bellman-Ford
hanya bisa mendeteksinya, dan algoritma ini tidak dapat menemukan shortest path
yang tidak mengulangi beberapa vertex dari graf semacam itu.
Menentukan vertex source dan daftar
seluruh vertices maupun edges · Assign nilai untuk distance dari vertex source
= 0, dan yang lain infinite ·
Mulailah iterasi terhadap semua
vertices yang dimulai dari vertex source, untuk menentukan distance dari semua
vertices yang berhubungan dengan vertex source dengan formula seperti berikut
ini :
–
U = vertex asal
–
V = vertex tujuan
–
UV = Edges yang menghubungkan U dan V
–
Jika distance V, lebih kecil dari distance U + weight UV maka distance V, diisi
dengan distance U + weight UV
–
Lakukan hingga semua vertices terjelajahi.
Untuk mengecek apakah ada negative
cycle dalam graf tersebut lakukan iterasi untuk semua edges yang ada, kemudian
lakukan pengecekan seperti dibawah ini: Untuk semua edges UV, jika ada distance
vertex U + weight edges UV kurang dari
distance vertex V maka sudah jelas bahwa graf tersebut memiliki negative cycle.
c. Algoritma Floyd
merupakan algoritma untuk pencarian
lintasan terpendek pada suatu graf berbobot (weighted graph). Algoritma
Floyd-Warshall membandingkan semua kemungkinan lintasan pada graf untuk setiap
sisi dari semua simpul. Cara kerja algoritma Floyd adalah sebagai berikut:
· Representasikan graf dengan N buah simpul dan bobotnya dengan
menggunakan dua buah matriks ketetanggaan, matriks M untuk bobot dan Matriks Z
untuk lintasan.
· Manipulasi keduanya sebanyak N iterasi.
· Matriks M hasil manipulasi akan menghasilkan bobot akhir
· Telusuri Matriks Z untuk mendapatkan lintasan terpendek
d. Algoritma Johnson
adalah algoritma yang digunakan untuk
mencari jarak terdekat, dimana di dalamnya juga terdapat algoritma Bellman Ford
dan algoritma Dijkstra dalam menentukan nilai-nilainya
· Langkah awal penyelesaian Algoritma Johnson adalah
mengkonstruksi digraph baru dengan menambahkan titik baru pada digraph dan
memberi bobot sisi yang keluar dari titik baru tersebut dengan 0.
· Langkah selanjutnya adalah mencari lintasan terpendek dari titik
baru ke semua titik lain. Lintasan terpendek tersebut digunakan untuk mengubah
bobot semua sisi pada digraph baru agar bobot semua sisi bernilai positif.
· Setelah itu mencari lintasan terpendek dari tiap titik ke semua
titik lain dan mengubah hasilnya dengan menggunakan lintasan terpendek dari
titik baru ke semua titik lain.
· SHasil dari perhitungan ini berupa matriks. Dari matriks ini
dapat diketahui panjang lintasan terpendek dari tiap titik ke semua titik lain.
a. Travelling Salesman Problem (TSP)
adalah suatu permasalahan dimana
seorang salesman harus mengunjungi semua kota dimana tiap kota hanya
dikunjunjungi sekali, dan dia harus mulai dari dan kembali ke kota asal.
Tujuannya adalah menentukan rute dengan jarak total atau biaya paling minimum
Salah satu algoritma yang dapat
dipakai yaitu algoritma Heuristik yang mencari nilai minimum bobot dengan
menggunakan spanning tree sehingga menghasilkan irisan dari graf yang memiliki
nilai optimal. Proses selanjutnya adalah membentuk sirkuit Euler. Lalu simpul
yang dilalui lebih dari satu kali diperbaiki sehingga menghasilkan solusi
paling optimal.
Langkah-langkahnya adalah sebagai
berikut:
· Cari minimum spanning tree yang menghubungkan tiap n simpul dari
graph yang kita namakan dengan network A
· Tentukan simpul graph berderajat, jika k jumlah simpul
berderajat ganjil, maka k pasti genap. Kita pasangkan k simpul sehingga
panjang cabang yang menghubungkan simpul minimum. Pasangan simpul yang
mempunyai nilai minimum membentuk jaringan yang dinamakan network B. Network A
dan B digabung menjadi network C.
· jaringan C tidak mempunyai simpul berderajat ganjil. Kita
dapat menggambarkan sirkuit Euler di network C. Network C merupakan aproksimasi
solusi dari travelling salesman problem.
· Periksa setiap simpul pada network C yang dikunjungi lebih dari
satu kali dan perbaiki solusi travelling salesman problem, dengan menerapkan
ketidaksamaan 1(a,b) < 1(a,c) + 1(b,c)
b. Chinese Postman Problem (CPP)
Masalah Chinese Postman Problem
pertama kali diformulasikan dalam bentuk masalah untuk menentukan sisi
terpendek bagi seorang tukang pos untuk melewati semua jalan yang ada dan
kembali ke tempat semula. Masalah ini dikemukakan oleh Kwan Mei-Ko di awal
1960-an dalam jurnal Chinese Mathematics. Dalam istilah graf definisi CPP
adalah mencari lintasan pada suatu graf berbobot yang terhubung yang melewati
semua sisi (minimal sekali) dengan jumlah bobot minimum dari suatu simpul
kembali ke simpul awal. Masalah ini dapat terjadi pada graf berarah, tidak
berarah, dan graf campuran. Solusi untuk graf tidak berarah dan berarah dapat
diselesaikan secara efisien dalam waktu polinomial, sedangkan solusi untuk graf
campuran ternyata sulit didapat (termasuk dalam kategori masalah NP-Complete).
Dasar untuk menyelesaikan masalah CPP adalah keberadaan sirkuit dan lintasan
Euler.
Algoritmanya adalah :
· Jika graf adalah graf genap, maka hanya menentukan jalur Euler
graf.
· Jika graf ganjil, maka:
· Menghitung dan kumpulkan simpul-simpul yang berderajat ganjil.
· Mencari jalur-jalur terpendek yang menghubungkan simpul-simpul
ganjil.
· Menggandakan jalur-jalur tersebut secara virtual yaitu dengan
melewat sisi dua kali
c. Coloring Grap
atau pewarnaan graf adalah pemberian
warna terhadap vertex-vertex graf dimana dua buah vertex yang berdampingan
tidak boleh mempunyai warna yang sama. G bewarna n artinya graf tersebut
menggunakan n warna. Bilangan kromatis dari G = K(G) adalah jumlah minimum
warna yang dibutuhkan.
Algoritma yang dapat digunakan untuk
menyelesaikan permasalahan pewarnaan graf salah satunya adalah algoritma
Greedy. Langkah-langkahnya sebagai berikut:
· - Inisialisasi himpunan solusi dengan kosong.
· - Urutkan vertex berdasarkan jumlah edge terbanyak.
· - Melakukan pemilihan vertex yang akan diisi warnanya dengan
fungsi seleksi vertex.
· Memilih kandidat warna dengan menggunakan kandidat kurangi warna
anggota himpunan kandidat dengan warna yang diambil. Periksa kelayakan warna yang dipilih menggunakan langkah ketiga.
Jika layak dimasukkan ke himpunan solusi. Periksa apakah solusi sudah meliputi pewarnaan seluruh vertex.
Jika sudah maka berhenti, jika belum maka akan kembali ke langkah ketiga.
d. Minimum Spanning Tree (MST)
merupakan cara menemukan jalan
terpendek dimana semua vertex telah terlewati sekali tanpa terjadi looping.
Salah satu algoritma yang dapat digunakan untuk menyelesaikannya yaitu
algoritma Prim.
Langkah-langkahnya sebagai berikut:
· - Pilih sisi graf G yang berbobot paling minimum dan masukkan ke
dalam T.
- Pilih sisi (u, v) yang mempunyai bobot minimum dan bersisian
dengan simpul di T, tetapi tidak membentuk sirkuit di T, lalu tambahkan ke
dalam T. Ulangi langkah kedua sebanyak n – 2 kali.
TREE
Pengertian Tree
Kumpulan node yang saling terhubung
satu sama lain dalam suatu kesatuan yang membentuk layakya struktur sebuah
pohon. Struktur pohon adalah suatu cara merepresentasikan suatu struktur
hirarki (one-to-many) secara grafis yang mirip sebuah pohon, walaupun pohon
tersebut hanya tampak sebagai kumpulan node-node dari atas ke
bawah. Suatu struktur data yang tidak linier yang menggambarkan hubungan yang
hirarkis (one-to-many) dan tidak linier antara elemen-elemennya.
Deklarasi Pohon
Jika kita memperhatikan setiap simpul
dalam pohon biner, kita bisa menyusun struktur data yang tepat dari
simpul-simpul tersebut. Kita dapat melihat bahwa dalam setiap simpul selalu
berisi dua buah pointer untuk menunjuk ke cabang kiri dan cabang kanan,
dan informasi yang akan disimpan dalamsimpul tersebut. Dengan memperhatikan hal
ini, simpul dalam pohon biner disajikan sebagai berikut:
Sesuai dengan gambar 7.1, maka
deklarasi list yang sesuai adalah:
typedef struct Simpul *Tree;
struct Simpul {
TypeInfo Info;
tree Kiri, /* cabang kiri */
Kanan; /* cabang kanan */
};
ISTILAH DALAM TREE
Jenis-jenis Tree
BINARY TREE
Tree dengan syarat bahwa tiap node
hanya boleh memiliki maksimal dua sub
pohon dan kedua subpohon harus
terpisah.
Kelebihan struktur Binary Tree :
·
Mudah dalam penyusunan algoritma
sorting
·
Searching data relatif cepat
·
Fleksibel dalam penambahan dan
penghapusan data
KUNJUNGAN PADA POHON BINER
Sebuah pohon biner memiliki
operasi traversal yaitu suatu kunjungan pada
suatu simpul tepat satu kali. Dengan
melakukan kunjungan lengkap kita akan
memperoleh urutan informasi secara
linier yang tersinpan di dalam pohon biner.
Terdapat tiga jenis kunjungan pada
pohon biner, yaitu :
PREORDER
Kunjungan jenis ini mempunyai urutan
kunjungan sebagai berikut :
· Cetak isi simpul yang dikunjungi.
· Kunjungi cabang kiri.
· Kunjungi cabang kanan.
Prosedur untuk melakukan traversal
secara PREORDER adalah sebagai berikut:
INORDER
Kunjungan jenis ini mempunyai urutan
kunjungan sebagai berikut :
· Kunjungi cabang kiri.
· Cetak isi simpul yang dikunjungi.
· Kunjungi cabang kanan.
Prosedur untuk melakukan traversal
secara INORDER adalah sebagai berikut:
POSTORDER
Kunjungan jenis ini mempunyai urutan
kunjungan sebagai berikut :
· Kunjungi cabang kiri.
· Kunjungi cabang kanan.
· Cetak isi simpul yang dikunjungi
BERIKUT MERUPAKN CONTOH PROGRAMNYA
#include<stdio.h>//header file
#include<conio.h>
/* Deklarasi struct */
typedef struct Node{
int
data; //data pada tree
Node
*kiri; //penunjuk node anak kiri
Node
*kanan; //penunjuk node anak kanan
};
/* Fungsi untuk memasukkan data ke
dalam tree */
void tambah(Node **root, int
databaru){
if((*root) == NULL){ //jika
pohon/subpohon masih kosong
Node *baru;//node “baru” dibentuk…
baru = new Node;//berdasarkan struct “Node”
baru->data = databaru; //data node baru diisi oleh variabel databaru
baru->kiri = NULL;//penunjuk kiri node baru masih kosong
baru->kanan = NULL;//penunjuk kanan node baru masih kosong
(*root) = baru; //node pohon (root) diletakkan pada node baru
(*root)->kiri = NULL;//penunjuk kiri node root masih kosong
(*root)->kanan = NULL; //penunjuk kanan node root masih kosong
printf(“Data bertambah!”);
}
else
if(databaru < (*root)->data)//jika databaru kurang dari data node root…
tambah(&(*root)->kiri, databaru);//tambahkan databaru pada subpohon
kiri
else
if(databaru > (*root)->data)//jika databaru lebih dari data node root…
tambah(&(*root)->kanan, databaru); //tambahkan databaru pada subpohon
kanan
else
if(databaru == (*root)->data)//jika databaru sama dengan data node root
printf(“Data sudah ada!”);//databaru tidak dapat ditambahkan pada tree
}
/* Fungsi untuk menampilkan data
secara pre-order
(data ditampilkan dari
node induk, node anak kiri, lalu node anak kanan)
*/
void preOrder(Node *root){
if(root != NULL){//jika pohon/subpohon tidak kosong
printf(“%d “, root->data);//menampilkan data node yang dikunjungi
preOrder(root->kiri);//mengunjungi node anak kiri
preOrder(root->kanan); //mengunjungi node anak kanan
}
}
/* Fungsi untuk menampilkan data
secara in-order
(data ditampilkan dari
node anak kiri, node induk, lalu node anak kanan)
*/
void inOrder(Node *root){
if(root != NULL){//jika pohon/subpohon tidak kosong…
inOrder(root->kiri);//mengunjungi node anak kiri
printf(“%d “, root->data);//menampilkan data node yang dikunjungi
inOrder(root->kanan);//mengunjungi
node anak kanan
}
}
/* Fungsi untuk menampilkan data
secara post-order
(data ditampilkan dari
node anak kiri, node anak kanan, lalu node induk)
*/
void postOrder(Node *root){
if(root !=
NULL){//jika pohon/subpohon tidak kosong
postOrder(root->kiri); //mengunjungi node anak kiri
postOrder(root->kanan);//mengunjungi node anak kanan
printf(“%d
“, root->data); //menampilkan data node yang dikunjungi
}
}
main(){
int pil, c;
Node *pohon,
*t;
pohon =
NULL;
do{
int data;
printf(“MENU\n”);
printf(“1. Tambah\n”);
printf(“2. Lihat Pre-Order\n”);
printf(“3. Lihat In-Order\n”);
printf(“4. Lihat Post-Order\n”);
printf(“5. Exit\n”);
printf(“Pilihan : “); scanf(“%d”, &pil);
switch(pil){
case 1 :
printf(“Data baru : “);
scanf(“%d”, &data);
tambah(&pohon, data);
break;
case 2 :
if(pohon != NULL)
preOrder(pohon);
else
printf(“Masih kosong!”);
break;
case 3 :
if(pohon != NULL)
inOrder(pohon);
else
printf(“Masih
kosong!”);
break;
case 4 :
if(pohon != NULL)
postOrder(pohon);
else
printf(“Masih kosong!”);
break;
}
getch();
printf(“\n”);
}
while(pil !=
5);
}
|
HASIL :
Daftar Pustaka :
~~~Terimakasih~~~
Postingan
0 komentar:
Posting Komentar