Graf adalah sekumpulan vertex/node yang dihubungkan oleh nol atau lebih edge.

• weight - "berat" dari suatu edge. dapat juga diartikan sebagai panjang sebuah edge.
• un/weighted graph - istilah dimana edge pada suatu graf memiliki/tidak memiliki weight.
• un/directed edge - istilah untuk menyatakan apabila sebuah edge bersifat dua arah/satu arah.
• path - urutan satu atau lebih edge yang dilewati untuk menghubungkan dua buah vertex.
• connected - sebuah graf dimana terdapat setidaknya satu buah path untuk setiap pasang vertex.
• cycle - sebuah path yang berawal dan berakhir pada satu buah vertex yang sama tanpa melewati dua buah edge yang sama.
• tree - sebuah undirected connected graf yang tidak memiliki cycle.
• root - vertex dengan kedalaman ter-rendah.
• ancestor - himpunan vertex yang dilewati dalam suatu path dari root ke sebuah vertex.
• parent - ancestor suatu node yang memiliki kedalaman tertinggi.
• child - kumpulan vertex yang terhubung dengan suatu edge dan bukan merupakan ancestor.

Terdapat 3 cara yang sering dipakai untuk merepresentasikan sebuah graf, yaitu

1. Adjacency Matrix
   Kita bisa merepresentasikan graf dengan menggunakan array 2 dimensi Adjmat[V][V] dengan AdjMat[i][j] bernilai 1 apabila terdapat edge yang menghubungkan vertex i dan vertex j dan 0 jika tidak ada. Nilai AdjMat[i][j] bisa juga bernilai weight dari suatu edge untuk weighted graf.
   Sebagai contoh, adjacency matrix untuk graf pada contoh adalah sebagai berikut:

0 1 0 0 1 0
1 0 1 0 1 0
0 1 0 1 0 0
0 0 1 0 1 1
1 1 0 1 0 0
0 0 0 1 0 0

2. Adjacency List
   Masalah utama dari penggunaan adjacency matrix adalah penggunaan memory yang menghabiskan sebanyak $V^2$ memory untuk graf dengan banyak vertex sebanyak $V$ sehingga tidak memungkinkan untuk graf dengan ukuran besar.
   Solusi permasalahan tersebut adalah dengan menggunakan Adjacency List. Ide dari perepresentasian dengan menggunakan Adjacency List adalah dengan hanya menyimpan daftar dari vertex-vertex lain yang memiliki edge yang terhubung dengan suatu vertex. Pengimplementasiannya dapat dilakukan dengan menggunakan vector seperti berikut:

vector< int > adjList[V];

//memasukkan edge a-b
adjList[a].push_back(b);
adjList[b].push_back(a);

untuk weighted graf kita dapat menggunakan pair<int,int> sebagai isi dari Adjacency List untuk menyimpan vertex yang adjacent beserta weightnya.
Berikut implementasi untuk weighted graf :

vector< pair<int,int> > adjList[V];

//memasukkan edge a-b dengan weight c
adjList[a].push_back(make_pair(b,c));
adjList[b].push_back(make_pair(a,c));

penggunaan metode ini dalam merepresentasikan graf sangat direkomendasikan karena sangat efisien dalam penggunaan memori maupun kompleksitas waktu dalam melakukan traversal.

3. Edge List
   Ide dari perepresentasian graf dengan metode ini adalah dengan menyimpan semua daftar edge yang ada dalam suatu graf. Penyimpanan dapat dilakukan di dalam sebuah array statis maupun dinamis seperti vector
   Pengimplementasiannya dapat menggunakan struct yang berisi vertex yang berada diujung edge tersebut beserta weight nya. Alternatif lain jika mager membuat struct adalah menggunakan sebuah pair<pair<int,int>,int> untuk menyimpan informasi yang dibutuhkan tadi.
   Contoh implementasinya adalah sebagai berikut:

vector< pair<pair<int,int>,int> > edgeList;

// memasukkan edge a-b dengan weight c
edgeList.push_back(make_pair(make_pair(a,b),c));

Untuk unweighted graf kita dapat mengganti isi dari vector menjadi pair<int,int>.
Metode ini sangat berguna dalam algoritma kruskal untuk mencari Minimum Spanning Tree dari sebuah graf
Note : meskipun terlihat sedikit lebih ribet, penulis lebih menyukai opsi menggunakan pair karena sesungguhnya pakai struct lebih malesin. ehe.

Dalam beberapa kasus, kita tidak memerlukan suatu struktur data khusus untuk menyimpan suatu graf agar bisa ditelusuru ataupun dioperasikan. Kasus-kasus tersebut terjadi jika graf berbentuk implicit graph.

2 Bentuk umum dari implicit graph yaitu :

1. Graf dengan edge yang implisit
   Contoh 1:
   Seperti yang kalian sering jumpai pada modul rekursi di dasar pemrograman, yaitu sebuah grid yang berisi karakter '.' ataupun '#' dimana kita tidak bisa mengunjungi grid yang berisi '#'. (Gambar A)
   Secara tidak sadar, ini adalah sebuah graf dengan vertexnya merupakan posisi yang berisi '.' serta edgenya menghubungkan dua buah '.' yang saling bersentuhan. (Gambar B)
   Dapat dilihat bahwa kita tidak memerlukan salah satu dari 3 teknik merepresentasikan graf seperti yang dijelaskan sebelumnya.
   Contoh 2:
   Graf yang dibentuk berdasarkan pergerakan bidak kuda pada permainan catur. Kita dapat menganggap petak-petak pada catur sebagai vertex dari graf, serta sebuah edge menghubungkan 2 buah petak jika petak tersebut dapat dikunjungi dengan melakukan langkah bidak kuda. (Gambar C)
2. Graf dengan edge yang mengikuti suatu peraturan
   Contoh:
   Graf dengan N vertex ([1..N]) dimana terdapat edge yang menghubungkan $i$ dan $j$ jika $(i+j)$ adalah prima. (Gambar D)