KATA PENGANTAR
Puji Syukur khadirat Allah Yang Maha Kuasa karena atas Rahmat dan
Hidayah-Nyalah kami dapat menyelesaikan Tugas Tengah Semester ini. Makalah ini merupkan salah satu bagian dalam
Tugas kami yang berjudul “GRAPH”. Terima kasih juga kepada Bapak
Marwan Hakim selaku dosen Pembimbing Mata
Kuliah Struktur Data di kelas kami Tekhik Informatika.
Makalah ini berisi tentang Pembelajaran mengenai “GRAPH” di dalam Struktur Data. Tentunya kami sangat berharap
Makalah ini dapat berguna bagi siapapun yang membacanya.
Masih banyak kekurangan dalam makalah ini . Selain itu dalam penyusunan tugas atau materi ini, tidak
sedikit hambatan yang penulis hadapi. Namun penulis menyadari bahwa kelancaran
dalam penyusunan materi ini tidak lain berkat bantuan, dorongan dan bimbingan orang
tua, sehingga kendala-kendala yang penulis hadapi teratasi
DAFTAR ISI
KATA
PENGANTAR ..................................................................................................... 2
DAFTAR
ISI..................................................................................................................... 3
I.
PENDAHULUAN........................................................................................................ 4
II. TEORI GRAPH........................................................................................................... 6
A. Definisi Graph.................................................................................................... 6
B. Istilah
dalam Graph............................................................................................ 9
C. Jenis – jenis Graph............................................................................................ 11
D. Konektivitas Tiap Jenis Graph......................................................................... 12
E. Metode Pencarian Vertex................................................................................. 14
a.
Depth First Search (DFS)............................................................................. 14
b.
Breadth First Search (BFS).......................................................................... 15
F. Shortest
Path...................................................................................................... 17
a.
Graph Berbobot (Weighted Graph)............................................................. 18
b.
Algoritma Dijkstra’s........................................................................................ 19
c.
Dinamic Programming.................................................................................. 19
G. Minimum
Spanning Tree.................................................................................. 21
H. Algoritma Menentukan Minimum Spanning Tree (MST)............................ 22
III. GRAPH PADA JAVA................................................................................................ 25
IV. KESIMPULAN........................................................................................................... 27
DAFTAR PUSTAKA...................................................................................................... 28
I. PENDAHULUAN
Dalam istilah ilmu komputer, sebuah
struktur data adalah cara penyimpanan,
pengorganisasian dan pengaturan data di dalam media
penyimpanan komputer sehingga data tersebut dapat digunakan
secara efisien. Dalam tehnik pemrograman, struktur data berarti tata letak data yang
berisi kolom-kolom data, baik itu kolom yang
tampak oleh pengguna (user) ataupun kolom yang hanya digunakan untuk keperluan
pemrograman yang tiadak tampak oleh pengguna.
Graph merupakan struktur data yang
paling umum. Jika struktur linear memungkinkan pendefinisian keterhubungan
sikuensial antara entitas data, struktur data tree memungkinkan pendefinisian
keterhubungan hirarkis, maka struktur graph memungkinkan pendefinisian
keterhubungan tak terbatas antara entitas data.
Banyak entitas-entitas data dalam
masalah-masalah nyata secara alamiah memiliki keterhubungan langsung
(adjacency) secara tak terbatas demikian. Contoh: informasi topologi dan jarak
antar kota-kota di pulau Jawa. Dalam masalah ini kota x bisa berhubungan
langsung dengan hanya satu atau lima kota lainnya. Untuk memeriksa
keterhubungan dan jarak tidak langsung antara dua kota dapat diperoleh
berdasarkan data keterhubungan-keterhubungan langsung dari kota-kota lainnya
yang memperantarainya.
Representasi
data dengan struktur data linear ataupun hirarkis pada masalah ini masih bisa
digunakan namun akan membutuhkan pencarian-pencarian yang kurang efisien.
Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga
pencariannya langsung (straightforward) dilakukan pada strukturnya sendiri.
Graf
adalah salah satu jenis struktur data yang terdiri dari titik (vertex) dan garis (edge), dimana dalam graf tersebut, vertex - vertex yang ada dihubungkan oleh edge, hingga menjadi suatu
kesatuan yang disebut graf. Sebagai
contoh dari pemodelan graf adalah peta kota kota, dimana kota disini sebagai
vertex dan jalur yang menghubungkannya berlaku sebagai edge.
Agar lebih jelas perhatikan gambar
dibawah ini :
Dalam gambar tersebut, terdapat
beberapa kota yang berada dipulau jawa dimana kota -
kota tersebut dihubungkan oleh beberapa jalur jalur yang ada. Untuk contoh
diatas kita bisa menganggap bawah kota-kota yang ada merupakan vertex,
dan jalur-jalur
yang menghubungkan kota-kota tersebut sebagai edge. Sehingga
secara keseluruhan peta diatas dapat dibuat pemodelannya sebagai sebuah graf.
Ada terdapat beberapa jenis graf yang
bisa kita gunakan, yaitu beberapa diantaranya adalah sebagai berikut :
•
Graf Berarah : adalah graf yang edge-nya memiliki arah, sebagai contoh edge AB
menghubungkan vertex A ke B, dimana hubungan vertex B ke A, harus diperoleh
dari edge lain, yaitu edge BA, dan jika edge BA tidak ada, maka vertex B ke A
tidak memiliki hubungan, meski vertex A ke B memiliki hubungan
•
Graf Tak Berarah : adalah graf yang edge-nya tidak memiliki arah, sehingga
jika edge AB menghubungkan vertex A ke B, maka secara otomatis juga
menghubungkan vertex B ke A.
•
Graf Berbobot : adalah suatu graf dimana edge dari graf tersebut memiliki bobot
atau nilai tertentu.
•
Graf Tidak Berbobot : adalah suatu graf dimana edge dari graf
tersebut tidak memiliki bobot atau nilai. Untuk merepresentasikannya dalam
pemrograman komputer, graf dapat disusun dari LinkedList yang berada dalam
LinkedList.
II. TEORI GRAPH
A.
Definisi Graph
Suatu graph didefinisikan oleh
himpunan verteks dan himpunan sisi (edge). Verteks menyatakan entitas-entitas
data dan sisi menyatakan keterhubungan antara verteks. Biasanya untuk suatu
graph G digunakan notasi matematis.
G = (V, E)
Dimana : G = Graph
V = Simpul atau
Vertex, atau Node, atau Titik
E = Busur atau
Edge, atau arc
V
adalah himpunan verteks dan E himpunan sisi yang terdefinisi antara
pasangan-pasangan verteks. Sebuah sisi antara verteks x dan y ditulis {x, y}. Suatu
graph H = (V1, E1) disebut subgraph dari graph G jika V1 adalah himpunan bagian
dari V dan E1 himpunan bagian dari E.
Cara
pendefinisian lain untuk graph adalah dengan menggunakan himpunan keterhubungan
langsung
Vx. Pada setiap verteks x terdefinisi Vx sebagai himpunan
dari verteks-verteks yang adjacent dari x. Secara formal:
Vx = {y | (x,y) -> E}
Dalam digraph didefinisikan juga
terminologi-terminologi berikut ini. Predesesor dari suatu verteks x
(ditulis Pred(x)) adalah himpunan semua verteks yang adjacent ke x.
Suksesor dari verteks x (ditulis Succ(x)) adalah himpunan semua verteks
yang adjacent dari x, yaitu adjacenct set
di atas.
Struktur data yang berbentuk
network/jaringan, hubungan antar elemen adalah many-to-many. Contoh dari graph adalah informasi topologi jaringan dan keterhubungan antar
kota-kota. Keterhubungan dan jarak tidak langsung antara dua kota sama dengan
data keterhubungan langsung dari kota-kota lainnya yang memperantarainya.
Penerapan struktur data linear atau hirarkis pada masalah graph dapat dilakukan
tetapi kurang efisien. Struktur data graph secara eksplisit menyatakan
keterhubungan ini sehingga pencariannya langsung (straight forward) dilakukan
pada strukturnya sendiri.
1. Struktur Data Linear = keterhubungan sekuensial
antara entitas data
2. Struktur Data Tree = keterhubungan hirarkis
3. Struktur Data Graph = keterhubungan tak terbatas
antara entitas data.
Representasi Graph dalam
Bentuk Matrik
a. Graph Tak Berarah
Graf tersebut dapat direpresentasikan
dalam sebuah matrik 5x5 , dimana baris dan kolom di matriks tersebut menunjukan
vertex yang ada.
b. Graph Berarah
Dalam matrik diatas dapat kita lihat
bahwa kotak yang berisi angka satu menunjukan bahwa dalam dua vertex tersebut
terdapat edge yang menghubungkannya. Dan jika dalam kotak terdapat angka nol,
maka hal tersebut menandakan tidak ada edge yang mengubungkan secara langsung
dua vertex tersebut.
Untuk representasi dalam pemorgraman
komputer, graf tersebut dapat digambarkan seperti dibawah ini :
B. Istilah Dalam Graph
1. Incident
Jika e merupakan busur dengan simpul-simpulnya adalah v dan w yang
ditulis e=(v,w), maka v dan w disebut “terletak” pada e, dan e disebut incident
dengan v dan w.
2. Degree
Didalam Graph ada yang disebut dengan Degree, Degree mempuyai 3 jenis antara lain :
·
Degree
dari suatu verteks x dalam undigraph adalah jumlah busur yang incident dengan simpul tersebut.
·
Indegree
dari suatu verteks x dalam digraph adalah jumlah busur yang kepalanya incident dengan simpul tersebut,
atau jumlah busur yang “masuk” atau menuju simpul tersebut..
·
Outdegree
dari suatu verteks x dalam digraph adalah jumlah busur yang ekornya incident dengan simpul tersebut,
atau jumlah busur yang “keluar” atau berasal dari simpul tersebut.
3.
Adjacent
Pada graph tidah berarah, 2 buah simpul
disebut adjacent bila ada busur yang menghubungkan kedua simpul tersebut.
Simpul v dan w disebut adjacent.
Pada graph berarah, simpul v disebut
adjacent dengan simpul w bila ada busur dari w ke v.
4. Successor dan Predecessor
Pada graph berarah, bila
simpul v adjacent dengan simpul w, maka simpul v adalah successor simpul w, dan
simpul w adalah predecessor dari simpul v.
5. Path
Sebuah path adalah
serangkaian simpul-simpul berbeda yang adjacent secara berturut-turut dari
simpul satu ke simpul berikutnya.
C.
Jenis -
Jenis Graph
1. Directed
Graph (Digraph)
Jika
sisi-sisi graph hanya berlaku satu arah. Misalnya : {x,y} yaitu arah x ke y,
bukan dari y ke x, x disebut origin dan y disebut terminus. Secara notasi sisi digraph ditulis
sebagai vektor (x, y).
Contoh
Digraph G = {V, E} :
V = {A, B,
C, D, E, F, G, H, I,J, K, L, M}
E = {(A,B),
(A,C), (A,D), (A,F), (B,C), (B,H), (C,E), (C,G),
(C,H), (C,I), (D,E), (D,F), (D,G), (D,K), (D,L), (E,F), (G,I), (G,K), (H,I), (I,J), (I,M), (J,K),
(J,M), (L,K), (L,M)}.
2. Graph Tak
Berarah (Undirected Graph atau Undigraph)
Setiap sisi
{x, y} berlaku pada kedua arah: baik x ke y maupun y ke x.
Secara grafis sisi pada undigraph tidak memiliki
mata panah dan secara notasional menggunakan kurung kurawal.
Contoh
Undigraph G = {V, E}
V = {A, B,
C, D, E, F, G, H, I,J, K, L, M}
E = {
{A,B},{A,C}, {A,D}, {A,F}, {B,C}, {B,H}, {C,E}, {C,G}, {C,H}, {C,I}, {D,E},
{D,F}, {D,G}, {D,K}, {D,L}, {E,F}, {G,I}, {G,K},
{H,I}, {I,J}, {I,M}, {J,K}, {J,M}, {L,K}, {L,M}}.
 |
Khusus
graph, undigraph bisa sebagai digraph (panah di kedua ujung edge
berlawanan) Struktur data linear maupun hirarkis
adalah juga graph. Node-node pada struktur linear ataupun hirarkis adalah
verteks-verteks dalam pengertian graph dengan sisi-sisinya menyusun node-node
tersebut secara linear atau hirarkis.
Struktur
data linear adalah juga tree dengan pencabangan pada setiap node hanya satu
atau tidak ada. Linear 1-way linked list (digraph), linear 2- way linked list
(undigraph).
D.
Konektivitas Tiap Jenis Graph
a. Konektivitas
pada Undigraph
·
Adjacency:
Dua verteks x dan y yang berlainan disebut berhubungan langsung
(adjacent) jika terdapat sisi {x, y} dalam E.
·
Path:
Sederetan verteks yang mana setiap verteks adjacent dengan verteks yang tepat
berada disebelahnya.
·
Panjang
dari path: jumlah sisi yang dilalui path.
·
Siklus:
suatu path dengan panjang lebih dari satu yang dimulai dan berakhir pada suatu
verteks yang sama.
·
Siklus
sederhana: dalan undigraph, siklus yang terbentuk pada tiga atau lebih
verteks-verteks yang berlainan yang mana tidak ada verteks yang dikunjungi
lebih dari satu kali kecuali verteks awal/akhir.
·
Dua
verteks x dan y yang berbeda dalam suatu undigraph disebut
berkoneksi (connected) apabila jika terdapat path yang menghubungkannya.
·
Himpunan
bagian verteks S disebut terkoneksi (connected) apabila dari setiap verteks x
dalam S terdapat path ke setiap verteks y (y bukan x)
dalam S.
·
Suatu
komponen terkoneksi (connected components) adalah subgraph (bagian dari graph)
yang berisikan satu himpunan bagian verteks yang berkoneksi.
·
Suatu
undigraph dapat terbagi atas beberapa komponen yang terkoneksi; jika terdapat
lebih dari satu komponen terkoneksi maka tidak terdapat path dari suatu verteks
dalam satu komponen verteks di komponen lainnya.
·
Pohon
bebas (free tree): suatu undigraph yang hanya terdapat satu komponen terkoneksi
serta tidak memiliki siklus sederhana.
b. Konektivitas pada Digraph
Terminologi di atas berlaku juga pada
Digraph kecuali dalam digraph harus dikaitkan dengan arah tertentu karena pada
arah yang sebaliknya belum tentu terdefinisi.
·
Adjacency
ke / dari: Jika terdapat sisi (x,y) maka dalam digraph dikatakan
bahwa x "adjacent ke" y atau y "adjacent
dari" x. Demikian pula jika terdapat path dari x ke y
maka belum tentu ada path dari y ke x Jadi dalam digraph
keterkoneksian didefinisikan lebih lanjut lagi sebagai berikut.
·
Terkoneksi
dengan kuat: Himpunan bagian verteks S dikatakan terkoneksi dengan kuat
(strongly connected) bila setiap pasangan verteks berbeda x dan y
dalam S, x berkoneksi dengan y dan y berkoneksi dengan x
(dpl., ada path dari x ke y dan sebaliknya dari y ke x).
·
Terkoneksi
dengan Lemah: Himpunan bagian verteks S dikatakan terkoneksi dengan lemah
(weakly connected) bila setiap pasangan verteks berbeda x dan y
dalam S, salah satu: x berkoneksi dengan y (atau y
berkoneksi dengan x) dan tidak kebalikan arahnya (dpl., hanya
terdefinisi satu path: dari x ke y atau sebaliknya dari y
ke x).
E.
Metode
Pencarian Vertex
Pencarian
vertex adalah proses umum dalam graph. Terdapat 2 metoda
pencarian, yakni
Depth First Search (DFS) dan Breadth First Search (BFS).
a.
Depth First
Search (DFS)
Pencarian
dengan metode ini dilakukan dari node awal secara mendalam
hingga yang paling akhir (dead-end) atau sampai ditemukan. Dengan kata lain, simpul cabang atau anak yang terlebih dahulu
dikunjungi.
Proses
pencarian dilakukan dengan mengunjungi cabang terlebih dahulu hingga tiba di
simpul terakhir. Jika tujuan yang diinginkan belum tercapai maka pencarian dilanjutkan ke
cabang sebelumnya, turun
ke bawah jika
memang masih ada cabangnya.
Begitu seterusnya hingga diperoleh tujuan akhir (goal). Depth First Search, memiliki kelebihan
diantaranya adalah cepat mencapai kedalaman ruang pencarian. Jika diketahui
bahwa lintasan solusi permasalahan akan
panjang maka Depth
First Search tidak
akan memboroskan waktu untuk
melakukan sejumlah besar
keadaan dangkal dalam permasalahan graf. Depth First Search
jauh lebih efisien untuk ruang pencarian
dengan banyak cabang
karena tidak perlu
mengeksekusi semua simpul pada suatu level tertentu pada daftar open.
Selain itu, Depth First Search
memerlukan memori yang
relatif kecil karena banyak node pada lintasan yang aktif
saja yang Selain kelebihan, Depth First Search juga memiliki kelemahan di
antaranya adalah memungkinkan tidak ditemukannya tujuan yang diharapkan dan
hanya akan mendapatkan
satu solusi pada
setiap pencarian.
b.
Breadth
First Search (BFS)
Prosedur
Breadth First Search (BFS) merupakan pencarian yang dilakukan dengan mengunjungi tiap-tiap node secara
sistematis pada setiap level hingga
keadaan tujuan (goal state)
ditemukan. Atau dengan kata
lain, penulusuran
yang dilakukan adalah
dengan mengunjungi tiap-tiap node pada level yang sama hingga ditemukan goal state-nya.
Implementasi
algoritma BFS :
Pengimplementasian
BFS dapat ditelusuri dengan menggunakan daftar (list), open, dan closed,
untuk menelusuri gerakan pencarian di dalam ruang keadaan.
Prosedur untuk Breadth First Search dapat dituliskan sebagai berikut:
Pada diatas, state 21 merupakan tujuannya (goal) sehingga bila ditelusuri menggunakan
prosedur Breadth First Search,
diperoleh:
1) Open = [1]; closed = [
].
2) Open = [2, 3, 4]; closed = [1].
3) Open = [3, 4, 5, 6]; closd = [2, 1].
4) Open = [4, 5, 6, 7, 8]; closed = [3, 2,
1].
5) Open = [5, 6, 7, 8, 9, 10]; closed = [4,
3, 2, 1].
6) Open = [6, 7, 8, 9, 10, 11, 12]; closed =
[5, 4, 3, 2, 1].
7) Open
= [7, 8,
9, 10, 11,
12, 13] (karena
12 telah di-open);
closed = [6,
5, 4, 3, 2, 1].
8) Open = [8, 9, 10, 11, 12, 13, 14]; closed
= [7, 6, 5, 4, 3, 2, 1].
9) Dan seterusnya sampai state 21 diperoleh
atau open = [ ].
Ada beberapa
keuntungan menggunakan algoritma
Breadth First Search ini, diantaranya adalah tidak akan menemui jalan
buntu dan jika ada satu
solusi maka Breadth First Search akan menemukannya, dan jika ada lebih
dari satu solusi
maka solusi minimum akan ditemukan.
Namun ada
tiga persoalan utama
berkenaan dengan Breadth First Search ini yaitu
:
1) Membutuhkan
memori yang lebih
besar, karena menyimpan semua
node dalam satu pohon.
2) Membutuhkan
sejumlah besar pekerjaan,
khususnya jika lintasan solusi
terpendek cukup panjang,
karena jumlah node yang
perlu diperiksa bertambah
secara eksponensial terhadap panjang lintasan.
3)
Tidak relevannya operator akan menambah jumlah node yang harus diperiksa.
Oleh karena
proses Breadth First Search mengamati
node di setiap level
graf sebelum bergerak
menuju ruang yang
lebih dalam maka mula-mula
semua keadaan akan
dicapai lewat lintasan
yang terpendek dari keadaan
awal. Oleh sebab
itu, proses ini
menjamin ditemukannya
lintasan terpendek dari
keadaan awal ke
keadaan tujuan (akhir). Lebih
jauh karena mula-mula
semua keadaan ditemukan melalui
lintasan terpendek sehingga setiap keadaan
yang ditemui pada kali
kedua didapati pada
sepanjang sebuah lintasan yang sama atau lebih panjang.
Kemudian, jika tidak ada kesempatan ditemukannya keadaan
yang identik pada
sepanjang lintasan yang lebih baik maka algoritma akan
menghapusnya
F. Shortest Path
Pencarian
shortest path (lintasan terpendek) adalah masalah umum dalam suatu weighted,
connected graph. Misal : Pencarian jaringan jalan raya yang menghubungkan
kota-kota disuatu wilayah.
1. Lintasan terpendek yag menghubungkan antara dua
kota berlainan tertentu (Single-source Single-destination Shortest
Path Problems)
2. Semua lintasan terpendek masing-masing dari suatu
kota ke setiap kota lainnya (Single-source Shortest Path problems)
3. Semua lintasan terpendek masing-masing antara tiap
kemungkinan pasang kota yang berbeda (All-pairs Shortest Path Problems)
Untuk
memecahkan masing-masing dari masalah-masalah tersebut
terdapat sejumlah solusi.
Dalam
beberapa masalah graph lain, suatu graph dapat memiliki bobot negatif dan kasus
ini dipecahkan oleh algoritma Bellman-Ford. Yang akan dibahas di sini adalah
algoritma Dijkstra yaitu mencari lintasan terpendek
dari suatu verteks asal tertentu vs ke setiap
verteks lainnya.
a. Graph berbobot (weighted graph)
Apabila
sisi-sisi pada graph disertai juga dengan suatu (atau beberapa) harga yang
menyatakan secara unik kondisi keterhubungan tersebut maka graph tersebut
disebut graph berbobot. Biasanya dalam masalah-masalah graph bobot tersebut
merupakan "harga" dari keterhubungan antar vertex.
Pengertian "harga" ini menggeneralisasikan banyak
aspek, biaya ekonomis dari proses/aktifitas,
jarak geografis/tempuh, waktu tempuh, tingkat kesulitan, dan lain sebagainya.
Dalam beberapa masalah lain bisa juga bobot
tersebut memiliki pengertian "laba" yang berarti kebalikan dari
"biaya" di atas. Dalam pembahasan algoritma-algoritma graph nanti
pengertian bobot akan menggunakan pengertian biaya sehingga apabila
diaplikasikan pada masalah yang berpengertian laba maka kuantitas-kuantitas
terkait adalah kebalikannnya. Misalnya mencari jarak tempuh minimum digantikan
dengan mencari laba maksimum.
b.
Algoritma Dijkstra’s
Algoritma Dijkstra's :
1. Menyelesaikan problem single-source shortest-path
ketika semua edge memiliki bobot tidak negatif.
2. Algoritma greedy mirip ke algoritma Prim's.
3. Algoritma di awali pada vertex sumber s, kemudian
berkembang membentuk sebuah tree T, pada akhirnya periode semua vertex
dijangkau dari S. Vertex di tambah ke T sesuai urutan
Misalnya :
Pertama S,
kemudian vertex yang tepat ke S, kemudian yang tepat berikutnya dan seterusnya.
c. Dynamic Programming
Terdiri dari
sederetan tahapan keputusan. Pada setiap tahapan berlaku prinsip optimality
(apapun keadaan awal dan keputusan yang diambil, keputusan berikutnya harus
memberikan hasil yang optimal dengan melihat hasil keputusan sebelumnya.
Misalnya : Multistage
Graph
Dimana
: Cost (i,j) =
Min(C(j,l) + Cost(i+1,l)}
Dengan
:
C(j,l) =
Bobot edge j dan l
l = Elemen
Vi+1 Dan <j,l> eemen E
i=stage ke-I
dan j = node dalam V
Proses dimulai dari k-2, dimana k adalah banyak stage.
Perhatikan contoh untuk menentukan biaya termurah dari 1 hingga 12.
Diketahui graph dengan stage sebagai berikut :
Maka langkah-langkah yang dilakukan adalah :
K=5, sehingga dimulai dari S3
Cost(3,6) = Min{6+Cost(4,9); 5+Cost(4,10)} = Min{6+4;5+2} = 7
Cost(3,7) = Min{4+Cost(4,9); 3+Cost(4,10)} = Min{4+4;3+2} = 5
Cost(3,8) = Min{5+Cost(4,10); 6+Cost(4,11)} = Min(5+2;6+5} = 7
Cost(2,2) = Min{4+Cost(3,6);2+Cost(3,7);1+Cost(3,8)}
= Min{4+7;2+5;1+7} = 7
Cost(2,3) = Min{2+Cost(3,6); 7+Cost(3,7)} = Min(2+7; 7+5) = 9
Cost(2,4) = Min{11+Cost(3,8)} = 18
Cost(2,5) = Min{11+Cost(3,7); 8+Cost(3,8)} = Min(11+5;8+7} = 15
Cost(1,1) = Min{9+Cost(2,2);7+Cost(2,3);3+Cost(2,4),2+Cost(2,5)}
= Min{9+7;7+9;3+18;2+15} = 16
Shorthest Path menjadi :
1 -> 3 -> 6 -> 10 -> 12 Atau 1 ->
2 -> 7 -> 10-> 12
Jika ada dua atau lebih shorthest path maka total biaya harus sama.
Shortest
Path Pertama adalah :
Shortest
Path Kedua adalah :
G. Minimum Spanning Tree
Definisi
Pohon rentangan atau spanning tree dari suatu connected graph didefinisikan
sebagai free-tree yang terbentuk dari subset sisi-sisi serta menghubungkan
setiap verteks dalam graph tersebut. Minimum Spanning
Tree (MST) adalah pohon rentangan dengan total bobot
dari sisi-sisinya adalah minimal. Dalam penelusuran vertex tidak
diperkenankan terbentuk siklus (cycle).
Diketahui
sebuah graph tak berarah dan tak berbobot sebagai berikut :
Kemungkinan Spanning Tree :
Bila jalur (edge) mempunyai biaya (cost) maka yang dicari adalah minimum
cost spanning tree.
H. Algoritma Menentukan Minimum Spanning Tree (MST)
Dua algoritma populer untuk menentukan minimum
spanning tree (MST) adalah Kruskal Algorithm dan
Prim’s Algorithm.
1. Algoritma Kruskal
Algoritma
ini lebih sederhana jika dilihat dari konsepnya namun lebih sulit dalam
implementasinya. Idenya adalah mendapatkan satu demi satu sisi mulai dari yang berbobot
terkecil untuk membentuk tree, suatu sisi walaupun berbobot kecil tidak akan
diambil jika membentuk siklik dengan sisi yang
sudah termasuk dalam tree. Yang menjadi masalah dalam implementasinya adalah keperluan
adanya pemeriksaan kondisi siklik tersebut.Salah satu pemecahaannya adalah
dengan subsetting yaitu pembentukan subset-subset yang disjoint dan secara bertahap dilakukan penggabungan
atas tiap dua subset yang berhubungan dengan suatu sisi dengan bobot terpendek.
Algoritma lengkapnya:
·
Tahap
pertama, jika dalam V terdapat n verteks maka diinisialisasi n buah subset yang
disjoint, masing-masing berisi satu verteks, sebagai subset-subset awal.
·
Tahap
berikutnya, urutkan sisi-sisi dengan bobot yang terkecil hingga terbesar.
·
Mulai dari
sisi dengan bobot terkecil hingga terbesar lakukan dalam iterasi: jika sisi
tsb. menghubungkan dua vertex dalam satu subset (berarti membentuk siklik) maka
skip sisi tersebut dan periksa sisi berikutnya jika tidak (berarti membentuk
siklik) maka kedua subset dari verteks-verteks yang bersangkutan digabungkan
menjadi satu subset yang lebih besar. Iterasi akan berlangsung hingga semua
sisi terproses.
MST_KRUSKAL (G)
{ For setiap vertex v dalam V[G] Do
{ set S(v) ←
{v} }
Inisialisasi priority queue Q yang berisi semua
edge dari G,
gunakan bobot sebagai keys.
A ← { } // A berisi edge dari MST
While A lebih kecil dari pada n-1 edge Do
{ set S(v) berisi v dan S(u) berisi u }
IF S(v) != S(u) Then
{ Tambahkan edge (u, v) ke A
Merge S(v) dan S(u) menjadi satu set
}
Return A
}
2. Algoritma Prim
Algoritma
dimulai dari suatu verteks awal tertentu dan bisa ditentukan oleh pemanggil
atau dipilih sembarang oleh algoritma. Misalnya verteks awal tersebut adalah v. Pada
setiap iterasi terdapat kondisi di mana himpunan vertex V terbagi dalam
dua:
W yaitu
himpunan verteks yang sudah dievaluasi sebagai node di dalam pohon, serta (V-W)
yaitu himpunan verteks yang belum dievaluasi.
Di awal
algoritma W diinisialisasi berisi verteks awal v. Selanjutnya, di dalam
iterasinya:
Pada setiap
adjacency dari tiap verteks dalam W dengan verteks dalam (V-W) dicari sisi
dengan panjang minimal. setelah diperoleh, sisi tersebut ditandai sebagai sisi
yang membentuk tree dan verteks adjacent sisi tersebut dalam (VW) dipindahkan
ke W (menjadi anggota W).
Jika sisi tersebut tidak ada maka proses selesai.
Dari contoh
di atas misalnya dilakukan pencarian mulai dari verteks A Maka algoritma ini
menghasilkan tahapan-tahapan iterasi pencarian sbb.:
MST_PRIM (G, w, v)
{ Q ← V[G]
for setiap u dalam Q do key [u] ← ∞
key [r] ← 0
π[r] ← NIl
while queue tidak kosong do
{ u ←
EXTRACT_MIN (Q)
for setiap
vertex v dalam Adj[u] do
{ if v ada
dalam Q dan w(u, v) < key [v] then
{ π[v] ←
w(u, v)
key [v] ←
w(u, v)
}
}
}
III. GRAPH PADA JAVA
Pada
Project ini, kita lakukan pengaplikasian dari teori Graph pada program Java.
Software yang kita gunakan adalah Eclipse.
Didalam Project ini terdapat 5
package Java. Dan yang akan kita bahas disini adalah Package GRAPH_BASIC.
Package GRAPH_BASIC, berisi 5 file berextensi .java yang saling berhubungan
satu sama lain. Untuk detail File bisa di lihat di gambar di bawah ini.
Untuk
melakukan Logika Aplikasi Graph terdapat pada File Main.java
Tampilan
Scriptnya seperti gambar di bawah ini.
Dapat
Kita lihat dari gambar diatas, logika Graph di mulai dari penambahan Vertex/Node,
dengan memanggil fungsi “AddVertex” pada file Graph.java. Setelah vertex
tercipta, dilakukan penambahan Edge/Busur dan terakhir memanggil fungsi untuk
menghasilkan output.
Untuk Output yang di hasilkan
bisa di lihat gambar di bawah ini.
IV.
KESIMPULAN
Mengenal Graph :
Ø Terdiri dari node dan
terdiri dari link
(busur)
Ø Node disebut vertex
dan Link disebut edge
Ø Informasi penting dalam graph adalah koneksi antar
vertex
Ø Pada undirected graph, tidak terdapat directions
(arah), Edge dari v0 ke v1 adalah sama dengan edge dari v1 ke v0
Ø Jika sebuah masalah dapat direpresentasikan ke
dalam bentuk kgraph maka
solusi dari masalah tersebut bisa dicari dengan bantuan graph
Ø Setiap vertex mewakili sebuah kondisi (state) dan
edge mewakili transisi antar state
Analogi Graph dalam Kehidupan Sehari-Hari
0 komentar:
Posting Komentar