Graph

Motivasi: Jaring-Jaring Kehidupan

Sejauh ini kita telah belajar menyusun data secara lurus berbaris (Linked List, Stack, Queue) dan secara hierarki atas-bawah (Tree). Namun, bagaimana jika kita ingin memodelkan data pertemanan di media sosial? Teman Anda bisa berteman dengan teman dari teman Anda, membentuk jaring-jaring yang saling silang.

Bagaimana dengan peta digital? Sebuah kota bisa memiliki banyak jalan yang terhubung ke berbagai kota lain, dan Anda bisa berputar-putar kembali ke kota asal.

Struktur data yang digunakan untuk memodelkan hubungan antar objek yang kompleks seperti ini disebut Graph. Graph digunakan di hampir seluruh teknologi modern:

• Media Sosial: Analisis jaringan pertemanan.
• Internet: Rute pengiriman paket data komputer.
• Sains: Memodelkan penyebaran penyakit atau jalur migrasi.

Anatomi Graph: $G = (V, E)$

Secara formal, sebuah Graph dibangun oleh dua elemen utama:

1. V (Vertices / Simpul): Sekumpulan titik atau objek data. Himpunan ini tidak boleh kosong.
2. E (Edges / Berus / Jalur): Sekumpulan garis yang menghubungkan simpul-simpul tersebut. Himpunan ini boleh kosong (simpul tidak terhubung).

Berdasarkan arah dan bobotnya, Graph dibagi menjadi:

• Directed Graph (Graf Berarah): Jalan satu arah. Jika A ke B, belum tentu B bisa kembali ke A.
• Undirected Graph (Graf Tak Berarah): Jalan dua arah (timbal balik).
• Weighted Graph (Graf Berbobot): Setiap jalur memiliki nilai, misalnya jarak (km) atau biaya tol.

Representasi Graph di Memori

Komputer tidak bisa "melihat" gambar jaring-jaring. Kita harus menerjemahkannya ke dalam susunan data:

1. Adjacency Matrix (Matriks Ketetanggaan)

Kita membuat tabel 2 Dimensi berukuran V x V.

• Baris dan kolom mewakili simpul.
• Sel tabel diisi 1 jika terhubung, dan 0 jika tidak.

Kelebihan: Sangat cepat untuk mengecek koneksi antar dua simpul. Kekurangan: Boros memori jika jumlah simpul sangat banyak namun jalurnya sedikit.

2. Adjacency List (Senarai Ketetanggaan)

Setiap simpul menyimpan daftar simpul tetangga yang terhubung dengannya. Biasanya menggunakan gabungan Array dengan Linked List.

Kelebihan: Hemat memori untuk jaringan yang luas tapi jalurnya sedikit. Kekurangan: Lebih lambat untuk mengecek koneksi spesifik karena harus menelurusi daftar daftar teman simpul tersebut.

Membuat Peta dengan Adjacency Matrix

Mari perhatikan kode simulasi di atas. Kita menggunakan GraphMat yang berisi tabel Array 2D matrix[5][5].

int main() {
    GraphMat peta;
    CreateEmptyGraph(&peta);

    // 1. Daftarkan Kota (Simpul)
    AddVertex(&peta, "Jakarta"); // Indeks 0
    AddVertex(&peta, "Bandung"); // Indeks 1
    AddVertex(&peta, "Semarang");// Indeks 2

    // 2. Hubungkan Kota (Bangun Jalur)
    AddEdge(&peta, 0, 1); // Jakarta <-> Bandung
    AddEdge(&peta, 1, 2); // Bandung <-> Semarang
    
    // Cek koneksi
    if (peta.matrix[0][2] == 1) {
        cout << "Ada jalan langsung Jakarta-Semarang";
    } else {
        cout << "Tidak ada jalan langsung Jakarta-Semarang";
    }

    return 0;
}