My first Magazine pemrograman-kompetitif-dasar | Page 99

9
Perkenalan Graf
Graf merupakan konsep matematika diskret untuk merepresentasikan objek-objek yang
saling berhubungan. Objek ini bisa saja berupa kota-kota yang terhubung dengan ruas jalan,
individu-individu manusia yang saling mengenal, atau hubungan mangsa-pemangsa antar hewan
di alam. Melalui pemahaman tentang konsep graf, kita dapat mendekati permasalahan yang
melibatkan hubungan antar objek dengan lebih baik. Kita juga akan mempelajari representasi graf
efisien dalam program sesuai dengan permasalahan yang ada.
9.1
Konsep Graf
Graf adalah struktur yang terdiri dari:
• Node /vertex , yaitu objek yang merepresentasikan suatu konsep.
• Edge , yaitu penghubung antar dua node .
Sebagai contoh, misalkan kita ingin memodelkan sejumlah kota yang dihubungkan oleh
beberapa ruas jalan dengan graf. Kita dapat menganggap setiap kota sebagai node , dan ruas
jalan sebagai edge .
A
E
D
B
C
Gambar 9.1: Node direpresentasikan dengan bentuk lingkaran dan edge direpresentasikan
dengan bentuk garis.
Gambar 9.1 menggambarkan:
• Terdapat lima kota, yaitu A, B, C, D, dan E.
• Terdapat sembilan ruas jalan, yaitu:
1. Antara kota A dengan kota B.
2. Antara kota A dengan kota C.
3. Antara kota A dengan kota E, sebanyak dua ruas.
4. Antara kota B dengan kota C, sebanyak dua ruas.
5. Antara kota C dengan kota D.
6. Antara kota C dengan kota E.
7. Antara kota D dengan kota E.
89