Hari ini kita akan melanjutkan materi struktur data dengan materi Graph, apa itu Graph? Graph adalah sekelompok simpul – simpul (nodes/vertices) V, dan sekelompok sisi (edges) E yang menghubungkan sepasang simpul. Bayangkan simpul tersebut sebagai lokasi, maka simpul tersebut adalah himpunan lokasi yang ada. Graph juga didefinisikan sebagai himpunan benda – benda yang disebut verteks (node) yang terhubung oleh sisi (edge/arc). Biasanya graph digambarkan sebagai kumpulan titik -titik (melambangkan verteks) yang dihubungkan oleh garis – garis.
Graph didalam sistematis dinyatakan sebagai berikut :
G = (V,E)
Dimana :
G = Graph
V = Simpul atau Vertex, atau Node, atau Titik
E = Busur atau Edge, atau arc
Macam – Macam Graph :
1. Undirected Graph
Graf yang sisinya tidak mempunyai orientasi arah disebut graph tak berarah. Pada graph tak berarah, urutan pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Perhatikan gambar dibawah ini :
dari contoh diatas dapat disimpulkan jika urutan sebuah simpul atau vertex tidak terlalu dipentingkan. Karena, contoh : E1 = A - B : B - A . Kenapa demikian? karena simpul dalam Graph tersebut tidak memiliki orientasi arah, jadi bisa dibilang E1 sama dengan vertex A ke B atau B ke A.
2. Directed Graph
Berbeda dengan Undirected Graph, Directed Graph setiap sisinya memiliki orientasi arah disebut sebagai Graph Berarah. Lain dengan Graph tak berarah, urutan pasangan simpul disini sangat diperhatikan karena dapat menyatakan hal yang berbeda. Perhatikan gambar dibawah ini :
Dari Graph diatas bisa disimpulkan bahwa setiap busur mempunyai tujuan yang berbeda - beda, seperti halnya E1 dan E2, mereka sama - sama menuju titik A dan B tetapi sebenarnya E1 dan E2 berbeda, karena E1 menuju dari A ke B, dan E2 dari B ke A (loh kan sama aja kalau begitu dengan Undirected Graph tadi?) jawabannya adalah berbeda karena E1 dan E2 memiliki jalur yang berbeda - beda.
3. Weighted Graph
Jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut mempunyai bobot. Perhatikan gambar dibawah ini :
Dari graph diatas, maksud dari angka angka tersebut adalah, contoh pada Titik A ke B memiliki bobot 10, nah bobot ini dapat dinyatakan sebagai panjang sebuah jalan dari dua buah titilk.
ISTILAH DALAM GRAPH :
1. Incident : Sebuah vertex/titik yang bertemu satu sama lain. Contoh, jika E merupakan busur dengan simpul - simpulnya adalah B dan A, maka ditulis E=(B,A), maka B dan A terletak pada E, dan E disebut incident dengan B dan A. Contoh gambar :
2. Degree (derajat)
Degree dari suatu sampul adalah jumlah busur yang incident dengan sampul tersebut.
Degree dibagi menjadi dua, yaiutu indegree dengan outdegree
a. Indegree
Indegree adalah sebuah busur yang kepalanya incident dengan simpul tersebut, atau menuju simpul tersebut. Contoh :
b. Outdegree
Outdegree adalah kebalikan dari Indegree dimana simpulnya incident dengan ekor dari simpul tersebut, atau berasal dari simpul tersebut. Contoh :
Nah, sampai disini dulu untuk materi hari ini, jika ada pertanyaan mengenai Graph tambahkan komentar dibawah.
Komentar
Posting Komentar