 |
GRAPH
G = (V, E)
G = (V, E)
Graph adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai :
G = (V, E)
Dimana :
G = Graph
V = Simpul
atau Vertex, atau Node, atau Titik
E = Busur
atau Edge, atau arc
ada beberapa
graph :
1. Graph tak
berarah (undirected graph atau non-directed graph) : Urutan simpul dalam
sebuah busur tidak dipentingkan. Mis busur e1 dapat disebut busur AB atau BA
Graph berarah
(directed graph) : Urutan simpul mempunyai arti. Mis busur AB adalah e1
sedangkan busur BA adalah e8.
2. 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.
Secara umum
terdapat dua macam representasi dari struktur data graf yang dapat
diimplementasi. Pertama, disebut adjacency list, dan
diimplementasi dengan menampilkan masing-masing simpul sebagai sebuah struktur
data yang mengandung senarai dari semua simpul yang saling berhubungan. Yang
kedua adalah representasi berupa adjacency matrix dimana
baris dan kolom dari matriks (jika dalam konteks implementasi berupa senarai
dua dimensi) tersebut merepresentasikan simpul awal dan simpul tujuan dan
sebuah entri di dalam senarai yang menyatakan apakah terdapat sisi di antara
kedua simpul tersebut.
Adjacency
List
Dalam teori
graf, adjacency list merupakan bentuk representasi dari seluruh sisi atau busur
dalam suatu graf sebagai suatu senarai. Simpul-simpul yang dihubungkan sisi
atau busur tersebut dinyatakan sebagai simpul yang saling terkait. Dalam
implementasinya, hash table digunakan untuk menghubungkan sebuah simpul dengan
senarai berisi simpul-simpul yang saling terkait tersebut.
Graf pada
gambar diatas dapat dideskripsikan sebagai senarai {a,b},{a,c},{b,c}. Dan
representasi adjacency list dapat digambarkan melalui tabel di bawah ini.
Tabel 1.
Representasi Adjacency List
|
Vertex
|
Adjacency
|
Array of Adjacent
|
|
a
|
adjacent to
|
b,c
|
|
b
|
adjacent to
|
a,c
|
|
c
|
adjacent to
|
a,b
|
Salah satu
kekurangan dari teknik representasi ini adalah tidak adanya tempat untuk
menyimpan nilai yang melekat pada sisi. Contoh nilai ini antara lain berupa
jarak simpul, atau beban simpul.
Adjacency
Matrix
Adjacency
Matrix merupakan representasi matriks nxn yang menyatakan hubungan antar simpul
dalam suatu graf. Kolom dan baris dari matriks ini merepresentasikan
simpul-simpul, dan nilai entri dalam matriks ini menyatakan hubungan antar
simpul, apakah terdapat sisi yang menghubungkan kedua simpul tersebut. Pada
sebuah matriks nxn, entri non-diagonal aij merepresentasikan sisi dari simpul i
dan simpul j. Sedangkan entri diagonal aii menyatakan sisi kalang(loop) pada
simpul i.
Gambar diatas
merupakan adjacency matrix yang berkorelasi dengan graf tak berarah pada gambar
4. Kolom dan baris pada matriks merupakan simpul- simpul berlabel 1-6.
Kelebihan dari adjacency matrix ini adalah elemen matriksnya dapat diakses
langsung melalui indeks, dengan begitu hubungan ketetanggan antara kedua simpul
dapat ditentukan dengan langsung. Sedangkan kekurangan pada representasi ini
adalah bila graf memiliki jumlah sisi atau busur yang relative sedikit, karena
matriksnya bersifat jarang yaitu hanya mengandung elemen bukan nol yang
sedikit. Kasus seperti ini merugikan, karena kebutuhan ruang memori untuk
matriks menjadi boros dan tidak efisien karena komputer menyimpan elemen 0 yang
tidak perlu.
3. .Istilah -
istilah
- Order;
Banyaknya simpul/vertex/node.
- Size;
Banyaknya garis/ruas/edge.
- Graph
Ekivalen Penggambaran graph yang sama. Di mana posisi elemen graph tidak
penting Multigraph; Graph yang disajikan secara
umum.
- Ruas
Berganda / Ruas Sejajar; 2 ruas yang memiliki titik ujung yang sama.
- Self
Loop; Edge yang dihubungkan oleh node ke dirinya sendiri.
- Simple
Graph; Tidak memiliki self loop atau pun multiple edge
Sangat bermanfaat
BalasHapusterimakasih kak
Hapus