Struktur Data Graph

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

• Sebuah graph mungkin hanya terdiri dari satu simpul
• Sebuah graph belum tentu semua simpulnya terhubung denga busur
• Sebuah graph mungkin mempunyai simpul yang tak terhubung dengan simpul lain
• Sebuah graph mungkin semua simpulnya saling berhubungan

Jenis Graph

1. Graph tak berarah (undirected graph atau non-directed graph) adalah urutan simpul dalam sebuah busur tidak dipentingkan, 
2. Graph berarah (directed graph) adalah urutan simpul mempunyai arti.
3. Graph berbobot (Weighted Graph) adalah jika setiap busur mempunyai nilai yang menyatakan hubungan antara 2 buah simpul, maka busur tersebut dinyatakan memiliki bobot, dan bobot sebuah busur dapat menyatakan panjang sebuah jalan dari 2 titik, jumlah rata-rata kendaraan perhari yang melalui sebuah jalan, dll.

Istilah pada Graph

• Incident; jika e merupakan busur dengan simpul-simpulnya adalah v dan w yang tertulis e=(v,w), maka v dan w disebut "terletak" pada e, dan e disebut incident dengan v dan w.
• Degree (derajat), indegree dan outdegree.
• Degree sebuah simpul adalah jumlah busur yang incident dengan simpul tersebut.
• Indegree sebuah simpul pada graph berarah adalah jumlah busur yang kepalanya incident dengan simpul tersebut, atau jumlah busur yang "masuk" atau menuju simpul tersebut.
• Outdegree sebuah simpul pada graph berarah adalah jumlah busur yang ekornya incident dengan simpul tersebut, atau jumlah busur yang "keluar" atau berasal dari simpul tersebut.
• Adjacent.
• pada graph tidak berarah, 2 (dua) buah simpul disebut adjacent bila ada busur yang menghubungkan kedua simpul tersebut.
• pada graph berarah, simbul v disebut adjacent dengan simpul w bila ada busur dari w ke v.
• Successor dan Predecessor. Pada graph berarah, bila simpul v adjacent dengan simpul w, maka simpul v adalah successor simpul w, dan simpul w adalah predecessor dari simpul v.
• Path. Sebuah path adalah serangkaian simpul-simpul yang berbeda, yang adjacent secara berturut-turut dari simpul satu ke simpul berikutnya.