GRAPH | WEIGHTED GRAPH | STRUKTUR DATA

GRAPH

A.   Graph adalah  sekelompok simpul-simpul (nodes/vertices) V, dan sekelompok sisi (edges) E yang menghubungkan sepasang simpul. Bayangkan simpul-simpul tersebut sebagai lokasi-lokasi, maka himpunan dari simpul-simpul tersebut adalah himpunan lokasi-lokasi yang ada. Dengan analogi ini, maka sisi merepresentasikan jalan yang menghubungkan pasangan lokasi-lokasi tersebut.
Graf juga didefinisikan sebagai himpunan benda-benda yang disebut verteks (node) yang terhubung oleh sisi (atau edge ata u arc). biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis (melambangkan sisi).
contoh implementasi graf pada struktur data :

-       Graf tak berarah (undirected graph)

Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak berarah. Pada graf tak-berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. salah satu contoh graf tak berarah dimana sisi-sisi yang menghubungkan antar simpul dalam graf tersebut tidak memiliki orientasi arah.

-        Graf Berarah (directed graph)

Graf yang setiap sisinya memiliki orientasi arah disebut sebagai graf berarah. Sisi berarah dalam graf ini dapat dinamakan sebagai busur (arc). Lain halnya dengan graf tak-berarah, urutan pasangan simpul disini sangat diperhatikan karena dapat menyatakan hal yang berbeda. contoh dari graf berarah yang memiliki sisi-sisi dengan orientasi arah (busur).

B.   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 "biaya" dari keterhubungan ybs. Pengertian "biaya" 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.

Oke langsung saja ke contoh kasusnya yaa^^

Disini terdapat suatu kasus, seperti pada gambar :

Nah, pada kasus di atas, kita di minta untuk menentukan beberapa hal, seperti :

1. Path

2.Jarak tempuh dari satu kota ke kota lain

3. Jarak terjauh

4 Jarak terpendek

oke, let's answer this amazing taks!!

1. Kita akan mencoba untuk membuat Parth jarak tempuh dari Jakarta - Blitar.

Perhatian contoh kasus pada gambar di atas tadi, hubungkan Path dari kota ke kota lainnya Mulai dari Jakarta hingga ke Blitar. Perhatikan jaraknya juga ya gaes^^ 

Nah, ini hasil yang aku kerjakan

NB : Bentuk Path dari kota ke kota lainya gak perlu persis letaknya seperti di peta ya. Ini free aja. Imagine it:D

Oke move ke taks ke 2, yaitu Menghitung Jarak tempuh tiap Path. Karena jalurnya sudah terbentuk, kita langsung hitung dari Jarak sesuai jalur yaa.

-       Jalur 1

Jakarta – Semarang – Banyuwangi – Blitar = 1650 km

-       Jalur 2

Jakarta – Semarang – Jogja – Malang – Banyuwangi – Blitar = 1500km

-       Jalur 3

Jakarta – Semarang – Jogja – Malang – Blitar = 870 km

-       Jalur 4

Jakarta – Jogja – Malang – Blitar = 970 km

-       Jalur 5

Jakarta – Jogja – Malang – Banyuwangi – Blitar = 1600 km

-       Jalur 6

Jakarta – Malang – Blitar = 920 km

-       Jalur 7

Jakarta – Malang – Banyuwangi – Blitar = 1550 km

Langsung move ke task 3 dan 4, menentukan jarak terpanjang dan terpendek. Tinggal pilih aja dari 7 jalur yang sebelumnya sudah di hitung mana jarak terpanjang dan terpendeknya.

3. Path terpanjang adalah Jalur 1

4. Path terpendek adalah Jalur 3

Yah, kira-kira seperti itulah pembahasan kita kali ini. Semoga bermanfaat^^