Graph Pada Struktur Data

Graph adalah sekelompok simpul - simpul ( node / vertices) V dan sekelompok sisi (edges) E yang menghubungkan sepasang simpul. dalam graph koneksi antar nodenya bersifat many to many, jadi setiap nodenya bisa terhubung lebih dari satu node lainnya

Jenis - jenis Graph :

Graph Berbobot (Weighted Graph)

Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot.

Bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.

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).

Tapi kali ini saya akan membahas tentang weighted graph

Dari gambar di atas tentukan:

1. Tentukan Path dari Jakarta ke madiun. (tuliskan semua jalur yang bisa dilalui)
2.  Berapakah jarak yang ditempuh untuk masing-masing path?
3. Path mana dan berapa jarak terpendek yang dapat ditempuh dari kedua kota itu
4. Path mana dan berapa jarak terjauh yang harus ditempuh dari kedua kota itu ?

Pertama kita harus membuat graph terlebih dahulu dari data diatas seperti di bawah ini

Nah setelah selesai membuat graphnya maka akan mudah menjawab pokok masalah yang ada di atas

1. Tuliskan path dari Jakarta ke Madiun (tuliskan semua jalur yang bisa dilalui)

1.  Jakarta – Malang – Madiun
2.  Jakarta – Jogja – Malang – Madiun
3.  Jakarta – Semarang – Jogja – Malang – Madiun

2. Berapakah jarak yang ditempuh dari masing-masing path ?

   

Jakarta – Malang – Madiun

   800 + 200 = 1.000

Jakarta – Jogja – Malang – Madiun

   600 + 250 + 200 =1.050

Jakarta – Semarang – Jogja – Malang – Madiun

   400 + 100 + 250 + 200 = 950

3. Path mana dan berapa jarak terpendek yang dapat ditempuh dari kedua kota itu ?

           

Jakarta – Semarang – Jogja – Malang – Madiun

      400 + 100 + 250 + 200 = 950

4. Path mana dan berapa jarak terjauh yang harus ditempuh dari kedua kota itu ?

Jakarta – Jogja – Malang – Madiun

      600 + 250 + 200 =1.050

nah itulah pengertian dari Weighted Graph dan untuk undirected graph dan directed graph akan saya bahas pada next pose 

terima kasih sudah mampir gan jangan lupa corat coret di bawah ya ☺☺☺