Konsep Graph

Banyak masalah nyata berbentuk jaringan: peta jalan antar kota, relasi pertemanan di media sosial, dependency antar modul pada proyek perangkat lunak, sampai koneksi neuron di otak. Semua fenomena ini berbagi pola yang sama — sekumpulan entitas yang saling berhubungan. Graph adalah struktur data formal untuk merepresentasikan pola tersebut: sekumpulan objek (vertex) beserta hubungan di antara mereka (edge). Pada Chapter ini kita akan mendefinisikan graph secara matematis, mengenali komponen penyusunnya, lalu memetakan contoh-contoh dunia nyata ke dalam notasi graph. Pemahaman ini menjadi fondasi sebelum kita memilih representasi memori dan algoritma yang tepat di Chapter-chapter selanjutnya.

Definisi Formal Graph #

Sebuah graph G didefinisikan sebagai pasangan terurut G = (V, E):

• V (Vertices) — himpunan node/titik. Setiap vertex adalah entitas yang ingin kita modelkan: kota, orang, modul, dsb.
• E (Edges) — himpunan hubungan antar vertex. Setiap edge berbentuk pasangan (u, v) yang menyatakan “ada hubungan antara u dan v”.

Jumlah vertex biasa ditulis |V| (atau n), jumlah edge |E| (atau m). Sebuah graph sederhana dengan 4 kota dan 5 jalur bisa direpresentasikan sebagai berikut:

Pada graph di atas, V = {Jakarta, Bandung, Cirebon, Yogyakarta} dan E = {(Jakarta,Bandung), (Jakarta,Cirebon), (Bandung,Cirebon), (Cirebon,Yogyakarta), (Bandung,Yogyakarta)}. Catatan: panah pada Mermaid hanya menandai arah gambar; graph ini bersifat undirected (hubungan dua arah) sehingga (Jakarta,Bandung) sama dengan (Bandung,Jakarta).

Komponen Penyusun Graph #

Sebelum melangkah ke implementasi, kita perlu menyepakati istilah dasar berikut:

• Vertex (plural: vertices) — objek individual dalam graph. Sering juga disebut node.
• Edge — hubungan antara dua vertex. Bisa berarah (panah) atau tidak berarah (garis).
• Neighbor / Adjacent — dua vertex disebut bertetangga bila terdapat edge yang menghubungkan keduanya.
• Loop — edge yang menghubungkan vertex dengan dirinya sendiri, contoh (A, A).
• Parallel edges — dua atau lebih edge identik menghubungkan pasangan vertex yang sama.

Berdasarkan ada/tidaknya loop dan parallel edges, graph dibagi menjadi:

Pada Course ini kita hampir selalu bekerja dengan simple graph kecuali dinyatakan lain, karena sebagian besar algoritma standar (BFS, DFS, Dijkstra, Kruskal) diasumsikan beroperasi pada simple graph.

Notasi Matematis Sederhana #

Mari kita lihat bagaimana graph dinyatakan secara konkret dengan C++. Pada Chapter ini kita baru memperkenalkan struktur dasar — implementasi penuh akan dibahas pada Chapter adjacency matrix / adjacency list.

#include <iostream>
#include <vector>
#include <string>

// Representasi graph sangat sederhana: daftar vertex dan daftar edge
struct Edge {
    int u;        // vertex sumber
    int v;        // vertex tujuan
};

int main() {
    // V = {0: Jakarta, 1: Bandung, 2: Cirebon, 3: Yogyakarta}
    const int V = 4;
    std::vector<std::string> names = {"Jakarta", "Bandung", "Cirebon", "Yogyakarta"};

    // E = 5 edge undirected
    std::vector<Edge> edges = {
        {0, 1},   // Jakarta - Bandung
        {0, 2},   // Jakarta - Cirebon
        {1, 2},   // Bandung - Cirebon
        {2, 3},   // Cirebon - Yogyakarta
        {1, 3},   // Bandung - Yogyakarta
    };

    std::cout << "Graph G = (V, E)\n";
    std::cout << "V = " << V << " vertices\n";
    std::cout << "E = " << edges.size() << " edges\n";

    std::cout << "\nDaftar vertex:\n";
    for (int i = 0; i < V; ++i) {
        std::cout << "  " << i << " -> " << names[i] << '\n';
    }

    std::cout << "\nDaftar edge (undirected):\n";
    for (const auto& e : edges) {
        std::cout << "  (" << names[e.u] << ", " << names[e.v] << ")\n";
    }
    return 0;
}

Output yang Dihasilkan:

Graph G = (V, E)
V = 4 vertices
E = 5 edges

Daftar vertex:
  0 -> Jakarta
  1 -> Bandung
  2 -> Cirebon
  3 -> Yogyakarta

Daftar edge (undirected):
  (Jakarta, Bandung)
  (Jakarta, Cirebon)
  (Bandung, Cirebon)
  (Cirebon, Yogyakarta)
  (Bandung, Yogyakarta)

1. Baris struct Edge { int u; int v; };: struktur minimal untuk satu edge. Pada Chapter ini kita belum memakai field weight — itu akan ditambahkan pada Chapter Weighted dan Unweighted Graph.
2. Baris const int V = 4;: jumlah vertex. Karena vertex diberi ID 0..V-1, kita dapat memakai array berindeks integer untuk hampir semua operasi graph.
3. Baris std::vector<Edge> edges = {{0, 1}, ...};: daftar edge disimpan sebagai vector of struct. Inilah benih representasi edge list yang akan dibahas tuntas pada Chapter khusus.
4. Catatan undirected: untuk graph undirected, pasangan (0, 1) menyiratkan hubungan dua arah. Kode di atas tidak menyimpan (1, 0) secara terpisah; saat traversal kita cukup menangani kedua arah dalam logika.

Contoh Graph di Dunia Nyata #

Banyak masalah yang awalnya tampak berbeda ternyata dapat dimodelkan sebagai graph. Tabel berikut memetakan beberapa domain populer:

Jenis-Jenis Graph Berdasarkan Struktur #

Selain berdasarkan loop/parallel edges, graph juga diklasifikasikan berdasarkan bentuk globalnya:

• Connected graph — pada undirected graph, setiap vertex dapat dicapai dari vertex lain melalui suatu path.
• Disconnected graph — terdiri dari dua atau lebih connected component yang terpisah.
• Complete graph (Kₙ) — setiap pasangan vertex terhubung oleh edge. Jumlah edge = n(n-1)/2.
• Tree — connected graph tanpa cycle. jumlah edge pasti V - 1.
• Bipartite graph — vertex dapat dipartisi menjadi dua himpunan sedemikian sehingga setiap edge menghubungkan vertex dari partisi berbeda.
• Directed Acyclic Graph (DAG) — directed graph tanpa cycle; dasar untuk topological sort.

Klasifikasi-klasifikasi ini akan kita pelajari satu per satu di Chapter berikutnya, lengkap dengan algoritma pendeteksinya (cycle detection, bipartite check, connected components).

Ringkasan #

• Graph G = (V, E) adalah struktur yang merepresentasikan hubungan antar objek.
• Vertex (node) = entitas; Edge = hubungan; neighbor = vertex yang bertetangga.
• Simple graph (tanpa loop dan parallel edges) adalah default di algoritma standar.
• Banyak masalah nyata dapat dimodelkan sebagai graph: social network, peta jalan, dependency, game state.
• Pilihan jenis graph (directed/undirected, weighted/unweighted, simple/multi) menentukan algoritma yang valid.
• Beri vertex ID integer 0..V-1 supaya seluruh operasi graph dapat memakai array berindeks.
• Bab-bab berikutnya akan membahas terminologi formal, jenis-jenis graph, lalu tiga representasi memori (matrix, list, edge list).