Pengertian Struktur Data Graph

Graf atau istilah aslinya Graph merupakan struktur data yang tersusun atas simpul-simpul atau titik-titik (Node) yang terhubung satu sama lain dengan garis-garis, yang mana jumlah garis ini tidak tentu. Masing-masing simpul diberi nama, lihat gambar contoh graf di bawah, nama-nama simpul adalah abjad A, B, C, .. sampai dengan F. Dan juga masing-masing garis memiliki bobot atau jarak, dalam gambar, bobot tersebut dinyatakan dengan abjad kecil a, b, c, .. sampai dengan h.

Karena Graf memiliki dua unsur yang terpisah, yaitu garis dan simpul, maka masing-masing dalam program harus dinyatakan dalam struktur data yang berbeda. Yang tampak jelas di sini yaitu garis menghubungkan dua simpul, tidak bisa lebih. Bisa dikatakan garis ini memiliki dua link yang menghubungkan simpul dan satu elemen data yang berisi bobot atau jarak.
Bentuk struktur data garis yaitu :

Type GarisPtr = ^GarisRec;
GarisRec = Record
Bobot : Integer; {Bisa juga real}
NodeKiri : NodePtr;
NodeKanan : NodePtr;
End;

Untuk simpul, dia bisa berisi segala macam tipe data. Dan karena simpul ini yang dihubungkan oleh garis, bukannya dia yang menghubungkan dirinya sendiri dengan simpul-simpul yang lain, maka struktur data untuk simpul bisa dibuat berdiri sendiri. Misalkan simpul berisi angka, maka dia bisa ditentukan tipenya berupa variabel integer atau real. Identifikasi tiap simpul dinyatakan dengan kode angka atau huruf.

Type NodePtr = ^NodeRec;
NodeRec = Record
Kode : Char;
{Bisa diganti dengan integer untuk kode angka}
..........
{Diisikan semua elemen data dalam satu node}
..........
End;

Node tidak memiliki link ke garis. Sebab satu simpul bisa saja terhubung sdengan banyak garis. Simpul hanya semata-mata berisi data yang berdiri sendiri.
Kemudian semua garis yang terbentuk tadi dikumpulkan dalam satu daftar, di sini kita pakai lagi senarai berantai. Urutan garis dalam daftar senarai bisa bebas, asalkan semua garis sudah masuk dalam daftar. Perlu diperhatikan bahwa suatu garis bisa saja menghubungkansatu simpul yang sama pada graf-graf tertentu. Begitu juga simpul yang tersusun, juga disimpan dalam daftar senarai berantai juga.