Struktur Data : Pengenalan Graph

📋 Daftar Isi

Apa itu Graph?

Graph adalah kumpulan node (simpul) di dalam bidang dua dimensi yang dihubungkan dengan
sekumpulan edge (garis). Graph dapat digunakan untuk merepresentasikan objek-objek diskrit (direpresentasikan sebagai node) dan hubungan antara objek-objek tersebut (direpresentasikan sebagai edge). Secara matematis dinyatakan sebagai:

\[ G = (V,E) \]

Dimana

\(G\) = Graph
\(V\) = Vertex, atau Node, atau Simpul, atau Titik
\(E\) = Edge, atau Busur, atau Garis

\(V\) terdiri dari \(v_{1},v_{2},…,v_{5}\)
\(E\) terdiri dari \(e_{1}, e_{2},…,e_{5}\)

Karakteristik Graph

Sebuah graph mungkin hanya terdiri dari satu node
Sebuah graph belum tentu semua nodenya terhubungan dengan edge
Sebuah graph mungkin mempunyai node yang tak terhubung dengan node yang lain
Sebuah graph mungkin semua nodenya salling berhubungan

Jenis-Jenis Graph

Graph Berarah

Graph Berarah (Directed Graph) dimana urutan node mempunyai arti. Misal node AB adalah e1
sedangkan busur BA adalah e8.

Graph Tak Berarah

Graph Tak Berarah (Undirected Graph atau Non-directed Graph) dimana urutan node dalam sebuah edge tidak dipentingkan. Misal edge e1 dapat disebut edge AB atau BA.

Graph Berbobot

Jika setiap edge mempunyai nilai yang menyatakan hubungan antara 2 buah node, maka edge
tersebut dinyatakan memiliki bobot. Bobot sebuah edge dapat menyatakan panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.

Istilah dalam Graph

Incident

Jika e merupakan edge dengan node-nodenya 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.

Adjacent

Dua buah node dikatakan berdekatan (adjacent) jika dua buah node tersebut terhubung dengan sebuah edge

Edge e3 = v2v3 incident dengan node v2 dan node v3, tetapi edge e3 = v2v3 tidak incident dengan node v1 dan node v4. Node v1 adjacent dengan node v2 dan node v3, tetapi node v1 tidak adjacent dengan node v4