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

• weight - "berat" dari suatu edge. dapat juga diartikan sebagai panjang sebuah edge.
• unweighted graph - istilah dimana edge pada suatu graf tidak memiliki weight.
• weighted graph - istilah dimana edge pada suatu graf memiliki weight.
• undirected edge - istilah untuk menyatakan apabila sebuah edge bersifat dua arah.
• directed edge - istilah untuk menyatakan apabila sebuah edge bersifat 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

   Adjacency Matrix adalah representasi graf yang menggunakan matrix berukuran $V*V$. Pada indeks dari matrix, digunakan nilai:

   • 0 jika tidak terdapat edge yang menghubungkan vertex i dengan vertex j.
   • 1 jika terdapat unweighted edge yang menghubungkan vertex i dengan vertex j.
   • weight jika terdapat weighted edge yang menghubungkan vertex i dengan vertex j.

   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

   Kelemahan dari adjacency matrix adalah penggunaan memory yang menghabiskan memory sebanyak $V^2$. Adjacency List menawarkan representasi graf yang lebih hemat dalam penggunaan memory. Ide dari perepresentasian dengan menggunakan Adjacency List adalah dengan hanya menyimpan daftar dari vertex-vertex lain yang memiliki edge yang terhubung dengan suatu vertex. Implementasiannya 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.

   Sebagai contoh, adjacency list untuk graf pada contoh adalah sebagai berikut:

   1: 2 5
   2: 1 3 5
   3: 2 4
   4: 3 5 6
   5: 1 2 4
   6: 4
   

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 adalah menggunakan 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>.

   Sebagai contoh, edge list untuk graf pada contoh adalah sebagai berikut:

   1, 2
   1, 5
   2, 3
   2, 5
   3, 4
   4, 5
   4, 6
   

   Metode ini sangat berguna dalam algoritma kruskal untuk mencari Minimum Spanning Tree dari sebuah graf.

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)

Lanjut ke Traversal Graf >