Representasi Graph Dalam Struktur Data

Representasi Matriks Keterhubungan Langsung (Adjacency Matrix)
Suatu matriks digunakan untuk menyatakan adjacency set setiap verteks dalam baris-barisnya. Nomor baris menyatakan nomor verteks adjacency berasal dan nomor kolom menunjukkan nomor verteks kemana arah adjacency. Elemen matriks [x, y] berharga 1 bila terdapat sisi dari x ke y dan berharga 0 bila tidak ada.

Harga biner ini memungkinkan penggunaan 1 bit untuk setiap sel matriks. Misalnya pada suatu graph dengan jumlah verteks 48 dapat digunakan 6 byte perbaris (semua 38 baris, jadi diperlukan 48 x 6 byte). Untuk mengetahui harga elemen matrilks maka diperlukan operasi shift-right serts operasi boolean and. Misalnya adjacency dari verteks 15 ke verteks 27 pada contoh 48 verteks di atas maka byte ke ë 27/8û dari baris ke 15 di-shift-right sebanyak (27 mod 8) posisi lalu di-and-kan dengan bilangan 1. Bila hasilnya 1 maka 15 adjacent ke 27, bila 0 maka tidak.
Direpresentasikan dalam matriks sbb.
Dari\Ke A B C D E F G H I J K L M
A - 1 1 1 0 1 0 0 0 0 0 0 0
B 1 - 1 0 0 0 0 1 0 0 0 0 0
C 1 1 - 0 1 0 1 1 1 0 0 0 0
D 1 0 0 - 1 1 1 0 0 0 1 1 0
E 0 0 1 1 - 1 0 0 0 0 0 0 0
F 1 0 0 1 1 - 0 0 0 0 0 0 0
G 0 0 1 1 0 0 - 0 1 0 1 0 0
H 0 1 1 0 0 0 0 - 1 0 0 0 0
I 0 0 1 0 0 0 1 1 - 1 0 0 1
J 0 0 0 0 0 0 0 0 1 - 1 0 1
K 0 0 0 1 0 0 1 0 0 1 - 1 0
L 0 0 0 1 0 0 0 0 0 0 1 - 1
M 0 0 0 0 0 0 0 0 1 1 0 1 -

Sudah tentu, representasi bit ini hanya dapat digunakan untuk graph yang tidak berbobot. Untuk graph berbobot maka diperlukan suatu matriks di mana setiap elemennya menyatakan harga (atau harga-harga) bobot tersebut. Adjacency secara implisit terepresentasikan dengan bobot-bobot ini. Bila harga bobot ¥ (tak hingga) maka berarti tidak terdapat sisi adjacent ybs.

Matriks ini digunakan baik untuk undigraph maupub digraph. Untuk undigraph maka matriks merupakan matriks simetris.
Dari\Ke A B C D E F G H I J K L M
A - 24 43 33 ¥ 31 ¥ ¥ ¥ ¥ ¥ ¥ ¥
B 24 - 18 ¥ ¥ ¥ ¥ 45 ¥ ¥ ¥ ¥ ¥
C 43 18 - ¥ 16 ¥ 22 35 15 ¥ ¥ ¥ ¥
D 33 ¥ ¥ - 19 22 39 ¥ ¥ ¥ 13 27 ¥
E ¥ ¥ 16 19 - 15 ¥ ¥ ¥ ¥ ¥ ¥ ¥
F 31 ¥ ¥ 22 15 - ¥ ¥ ¥ ¥ ¥ ¥ ¥
G ¥ ¥ 22 39 ¥ ¥ - ¥ 21 ¥ 13 ¥ ¥
H ¥ 45 35 ¥ ¥ ¥ ¥ - 25 ¥ ¥ ¥ ¥
I ¥ ¥ 15 ¥ ¥ ¥ 21 25 - 19 ¥ ¥ 35
J ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ 19 - 10 ¥ 15
K ¥ ¥ ¥ 13 ¥ ¥ 13 ¥ ¥ 10 - 19 ¥
L ¥ ¥ ¥ 27 ¥ ¥ ¥ ¥ ¥ ¥ 19 - 25
M ¥ ¥ ¥ ¥ ¥ ¥ ¥ ¥ 35 15 ¥ 25 -
Representasi List Keterhubungan Langsung (Adjacency List)
Mengingat bahwa rasio degree (atau outdegree pada digraph) rata-rata verteks terhadap jumlah verteks dalam sejumlah masalah adalah bisa sangat kecil maka representasi matriks tersebut akan berupa matriks sparse yaitu sebagian besarnya berisikan bilangan nol (atau bilangan ¥ pada weighted graph). Untuk kepentingan efisiensi ruang maka tiap baris matriks tersebut digantikan list yang hanya berisikan verteks-verteks dalam adjacency set Vx dari setiap verteks x.

Keseluruhan graph adalah array dari verteks yang pada masing-masing verteksnya digunakan suatu struktur list untuk menyimpan indeks-indeks dari verteks yang adjacent dari verteks yang bersangkutan. Jika list menggunakan fixed array maka perlu disimpan pula degree (atau out degree) yang menyatakan panjang dari list. Jika menggunakan list berkait maka informasi degree ini tidak diperlukan.

Pada masalah yang sangat dinamis di mana selama proses berlangsung bisa muncul verteks baru atau dihapusnya suatu verteks yang ada dari graph maka struktur array untuk verteks ini dapat menggunakan suatu list berkait pula. Pada struktur demikian maka list dari adjacent verteks berisikan pointer dari verteks-verteks. Secara keseluruhan apabila adjacent list menggunakan list berkait pula, graph direpresentasikan dengan multilevel linked-list.