Materi 02 : Struktur Data Graph

Juli 16, 2026

Materi Ajar: Struktur Data Graph | Informatika Kelas IX

🎯 Tujuan Pembelajaran

Menjelaskan pengertian dan komponen struktur data Graph (vertex/node dan edge).
Membedakan jenis-jenis Graph (berarah/tidak berarah, berbobot/tidak berbobot).
Menerapkan struktur Graph untuk merepresentasikan hubungan antarentitas dalam kehidupan sehari-hari (jaringan sosial, peta jalan/rute).
Merancang dan mempresentasikan proyek mini penerapan struktur Graph pada suatu permasalahan nyata.

Yuk, Pikirkan Dulu…

Pernahkah kalian menggunakan aplikasi peta digital untuk mencari rute tercepat ke suatu tempat? Bagaimana menurut kalian aplikasi tersebut bisa menemukan jalan yang paling pendek dari sekian banyak pilihan jalan?

1 Mengenal Struktur Data Graph

Pada materi sebelumnya, kalian telah mempelajari Tree — struktur data yang tersusun berjenjang, di mana setiap simpul hanya punya satu induk. Sekarang, mari kita kenali struktur data lain yang lebih "bebas": Graph.

Struktur Data Graph adalah struktur data yang terdiri dari sekumpulan simpul (vertex/node) yang saling terhubung melalui sisi (edge). Berbeda dengan Tree, pada Graph setiap simpul bisa terhubung ke simpul mana saja, bahkan bisa membentuk siklus (kembali lagi ke simpul awal)!

Bayangkan peta kota: setiap kota adalah vertex, dan setiap jalan yang menghubungkan dua kota adalah edge. Sebuah kota bisa terhubung langsung ke banyak kota lain sekaligus — tidak ada aturan "satu induk satu anak" seperti pada Tree.

Setiap kota (vertex) dapat terhubung ke lebih dari satu kota lain. Perhatikan Kota B dan Kota C terhubung langsung (garis putus-putus) sekaligus membentuk siklus melalui Kota A, D, dan E.

Komponen Utama Graph

Vertex / NodeElemen dasar yang mewakili suatu entitas dalam Graph, misalnya sebuah kota, orang, atau halaman web.

Edge (sisi)Garis penghubung yang menyatakan adanya hubungan antara dua vertex.

Bobot (weight)Nilai yang melekat pada edge, menyatakan "kekuatan" atau "jarak" hubungan — misalnya jarak tempuh dalam km.

Arah (directed)Sifat edge yang menunjukkan hubungan satu arah antar vertex, ditandai dengan tanda panah.

Tree vs Graph, Apa Bedanya?

Sebenarnya, Tree adalah "kasus khusus" dari Graph! Bedanya, pada Tree setiap simpul (kecuali root) hanya boleh punya satu induk dan tidak boleh membentuk siklus. Pada Graph, aturan ketat itu tidak ada — simpul bebas terhubung ke simpul manapun, bahkan bisa kembali ke simpul awal (membentuk siklus/loop).

2 Jenis-Jenis Graph

Berdasarkan sifat hubungannya, Graph dapat dibedakan menjadi tiga jenis utama:

A. Undirected Graph (Graph Tak Berarah)

Pada Undirected Graph, edge tidak memiliki arah — artinya hubungan antara dua vertex berlaku dua arah sekaligus. Contoh: pertemanan di Facebook (jika A berteman dengan B, maka B otomatis berteman dengan A juga), atau jalan dua arah.

Undirected Graph: garis tanpa panah menandakan hubungan pertemanan berlaku dua arah antara Ani, Budi, dan Citra.

B. Directed Graph (Graph Berarah)

Pada Directed Graph, setiap edge memiliki arah (ditandai anak panah) yang menunjukkan hubungan satu arah. Contoh: fitur "follow" di Instagram (jika A follow B, B belum tentu follow balik A), atau arus lalu lintas satu arah.

Directed Graph: @ani follow @budi, @citra follow @budi, dan @citra follow @ani — namun @budi tidak follow siapa pun balik.

C. Weighted Graph (Graph Berbobot)

Pada Weighted Graph, setiap edge memiliki nilai/bobot yang menyatakan jarak, biaya, atau waktu tempuh. Contoh paling umum: peta jalan dengan jarak antar kota dalam kilometer.

Weighted Graph: setiap edge memiliki angka bobot (jarak dalam km) antara Kota A, B, dan C.

Ringkasan Perbandingan Jenis Graph

Jenis Graph	Ciri Utama	Contoh Penerapan
Undirected	Edge tanpa arah, hubungan dua arah	Pertemanan Facebook, jalan dua arah
Directed	Edge memiliki arah (panah), hubungan satu arah	Follow Instagram, arus lalu lintas satu arah
Weighted	Edge memiliki nilai/bobot (jarak, biaya, waktu)	Peta jalan dengan jarak antar kota

Latihan Klasifikasi Cepat

Coba pikirkan, termasuk jenis Graph apakah kasus-kasus berikut ini?

Aplikasi Ojek Online

Peta lokasi driver & penumpang dengan estimasi jarak → Weighted Graph

Grup WhatsApp Keluarga

Semua anggota bisa saling chat dua arah → Undirected Graph

Subscribe Kanal YouTube

Kamu subscribe kanal, kanal tidak subscribe balik → Directed Graph

3 Penerapan Graph: Rute Perjalanan & Jaringan Sosial

A. Mencari Rute Terpendek

Salah satu manfaat terbesar Weighted Graph adalah membantu menemukan rute terpendek atau tercepat — persis seperti yang dilakukan aplikasi peta digital pada pertanyaan pemantik di awal!

Peta lima kota (A, B, C, D, E) beserta jarak (bobot) tiap jalan. Tugas kita: mencari rute terpendek dari Kota A menuju Kota D.

Perhatikan, ada beberapa kemungkinan jalur dari A menuju D. Mari kita hitung total jarak setiap jalur satu per satu:

Jalur 1: A → B → D = 10 km + 15 km = 25 km

Jalur 2: A → E → D = 25 km + 8 km = 33 km

Jalur 3: A → B → C → D = 10 km + 12 km + 18 km = 40 km

Kesimpulan

Dari ketiga jalur di atas, Jalur 1 (A → B → D) sepanjang 25 km adalah rute terpendek! Inilah prinsip dasar yang digunakan aplikasi peta digital: membandingkan total bobot dari berbagai kemungkinan jalur, lalu memilih yang paling kecil (atau paling cepat).

🎯 Coba Sendiri: Tebak Rute Terpendek

Perhatikan kembali peta lima kota di atas. Menurutmu, manakah rute terpendek dari Kota A ke Kota C? Klik salah satu pilihan di bawah untuk memeriksa jawabanmu.

B. Graph pada Jaringan Sosial

Pernahkah kalian melihat fitur "Teman yang mungkin kamu kenal" di media sosial? Fitur ini bekerja dengan menganalisis Graph pertemanan: jika si A dan si C memiliki banyak teman yang sama (koneksi/edge yang sama), sistem akan merekomendasikan agar A dan C berteman juga — karena kemungkinan besar mereka saling kenal.

Rani dan Dimas sama-sama berteman dengan Sari dan Bayu (koneksi/edge yang sama), sehingga sistem merekomendasikan agar Rani dan Dimas juga berteman.

✓ Rangkuman

Poin-Poin Penting

Graph adalah struktur data berisi vertex (simpul) yang saling terhubung melalui edge (sisi), tanpa aturan hierarki seperti Tree.
Komponen utama Graph: vertex/node, edge, bobot (weight), dan arah (directed).
Undirected Graph: edge tanpa arah, hubungan dua arah (contoh: pertemanan Facebook).
Directed Graph: edge memiliki arah, hubungan satu arah (contoh: follow Instagram).
Weighted Graph: edge memiliki bobot/nilai, digunakan untuk menghitung rute terpendek (contoh: peta jalan).
Graph banyak diterapkan pada aplikasi peta digital dan rekomendasi teman di media sosial.

? Uji Pemahaman

Jawablah pertanyaan berikut untuk menguji pemahaman kalian. Klik salah satu pilihan jawaban!

1. Elemen yang mewakili suatu entitas (misalnya kota atau orang) dalam Graph disebut…

2. Fitur "follow" pada Instagram adalah contoh penerapan jenis Graph…

3. Pada peta jalan yang mencantumkan jarak antar kota dalam km, nilai jarak tersebut disebut…

4. Pertemanan di Facebook (jika A berteman B, otomatis B berteman A) adalah contoh…

5. Perbedaan mendasar antara Tree dan Graph adalah…

✎ Proyek Mini

Merancang Graph untuk Permasalahan Nyata

Bersama kelompok (4–5 orang), rancanglah sebuah struktur Graph lengkap dengan vertex dan edge, serta tentukan apakah Graph kalian berarah/tidak berarah dan berbobot/tidak berbobot, untuk salah satu tema berikut. Tuangkan hasilnya dalam bentuk diagram pada kertas plano atau aplikasi presentasi digital, lalu presentasikan di depan kelas.

Pilihan 1Peta rute perjalanan dari rumah ke sekolah untuk beberapa siswa.

Pilihan 2Graph jaringan pertemanan satu angkatan.

Pilihan 3Graph alur distribusi tugas piket kelas.

Ingat: pastikan rancangan Graph kalian konsisten — jika memilih berarah, gunakan tanda panah pada semua edge; jika berbobot, cantumkan nilai pada semua edge!