Struktur data graph adalah representasi visual dari kumpulan objek yang terhubung satu sama lain dengan menggunakan simpul (node) dan sisi (edge). Graph adalah salah satu jenis struktur data yang berguna untuk menyimpan dan memanipulasi hubungan antara entitas dalam bentuk grafis.
Struktur data graph terdiri dari dua komponen utama: simpul dan sisi. Simpul (node) adalah entitas individu dalam graph, sedangkan sisi (edge) adalah hubungan antara dua simpul. Setiap sisi memiliki dua ujung yang menunjuk pada dua simpul yang berbeda atau pada simpul yang sama dalam kasus sisi lingkaran (self-loop).
Ada beberapa jenis graph yang umum digunakan, antara lain:
- Graph tak berarah (undirected graph): Pada jenis graph ini, sisi tidak memiliki arah atau orientasi tertentu. Artinya, hubungan antara dua simpul adalah saling dua arah. Contohnya adalah hubungan pertemanan antara individu dalam jaringan sosial.
- Graph berarah (directed graph): Pada jenis graph ini, setiap sisi memiliki arah atau orientasi tertentu. Artinya, hubungan antara dua simpul memiliki arah tertentu, misalnya dari simpul A ke simpul B, tetapi tidak berlaku sebaliknya. Contohnya adalah hubungan antara dua kota dalam sistem transportasi.
- Graph berbobot (weighted graph): Pada jenis graph ini, setiap sisi memiliki bobot yang diberikan untuk menggambarkan tingkat pentingnya atau jarak antara dua simpul. Bobot dapat berupa angka, jarak fisik, biaya, atau atribut lain yang relevan. Contohnya adalah jarak antara dua lokasi dalam peta.
Graph dapat diimplementasikan dalam berbagai cara, termasuk menggunakan struktur data seperti matriks adjasensi, daftar adjasensi, atau melalui representasi objek. Setiap metode implementasi memiliki kelebihan dan kelemahan tersendiri tergantung pada kebutuhan dan operasi yang dilakukan pada graph.
Struktur data graph sangat berguna dalam berbagai bidang seperti pemodelan jaringan sosial, pemetaan jaringan komputer, analisis rute, optimisasi jaringan, perutean paket, dan banyak lagi.