GRAPH PADA JAVA

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

Graph dalam kehidupan sehari-hari dapat dianalogikan sebagai suatu jaringan satu dengan jaringan lainnya yang saling terhubung. Misal seperti negara Indonesia yang memiliki banyak kota seperti: Jakarta, Bandung, Surabaya, Yogyakarta. Kota-kota itulah yang tergabung dalam negara Indonesia dan kota-kota itulah yang saling berhubungan.

Algoritma Menentukan Minimum Spanning Tree (MST)

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)

}

}

}