Graph adalah kumpulan titik yang disambung garis. Titiknya disebut node (atau vertex), garisnya disebut edge. Contoh paling gampang: peta, dengan kota sebagai node dan jalan antar kota sebagai edge. Media sosial juga graph: orang adalah node, pertemanan adalah edge.
🧪 Tebakan cepat: ada jalan antara Jakarta dan Bandung. Kalau kamu tanya Bandung "tetanggamu siapa saja?", apa Jakarta ikut disebut? Tebak dulu, jawabannya ada di bagian "Node, edge, dan tetangga".
Node, edge, dan tetangga
Jakarta ----- Surabaya
| |
Bandung ----- Yogya
Peta ini punya 4 node (kota) dan 4 edge (jalan). Di kode, graph biasanya disimpan sebagai adjacency list: tiap node punya array berisi tetangganya.
const graph = {
Jakarta: ["Bandung", "Surabaya"],
Bandung: ["Jakarta", "Yogya"],
Yogya: ["Bandung", "Surabaya"],
Surabaya: ["Yogya", "Jakarta"],
};
console.log(graph["Jakarta"]); // ["Bandung", "Surabaya"]
console.log(graph["Jakarta"].length); // 2
- Tetangga (neighbor) sebuah node adalah node yang tersambung langsung lewat satu edge. Tetangga Jakarta: Bandung dan Surabaya.
graph["Jakarta"]langsung memberi semua tetangga Jakarta, tanpa mencari.- Degree adalah jumlah tetangga sebuah node, yaitu panjang array-nya. Degree Jakarta: 2.
- Tiap jalan tercatat dua kali, sekali di tiap ujungnya: jalan Jakarta dan Bandung muncul di array Jakarta dan di array Bandung. Jadi ya, Bandung menyebut Jakarta. Itu jawaban tebakannya.
Jalan dari Jakarta ke Bandung, Yogya, Surabaya, lalu balik ke Jakarta membentuk cycle: jalur yang kembali ke titik awalnya. Tree yang sudah kamu kenal sebenarnya graph yang semua node-nya tersambung dan gak punya cycle. Graph lebih bebas: boleh ada cycle, dan satu node boleh tersambung ke siapa saja.
Arah dan bobot
- Undirected (tanpa arah): edge berlaku dua arah. Jalan antara A dan B bisa dilewati bolak-balik, jadi A ke B sama dengan B ke A. Contohnya pertemanan.
- Directed (berarah): edge punya arah, jadi A → B belum tentu B → A. Contohnya follow di Instagram: kamu follow seseorang, dia belum tentu follow balik. Di adjacency list, tiap node cuma mencatat edge yang keluar darinya.
- Weighted (berbobot): tiap edge punya angka, misalnya jarak dalam km. Unweighted: semua edge dianggap sama.
Membuatnya dengan class dan Map
class Graph {
constructor() {
this.adjacency = new Map(); // node → array tetangga
}
addVertex(v) {
if (!this.adjacency.has(v)) this.adjacency.set(v, []);
}
addEdge(v1, v2) {
this.addVertex(v1); // node yang belum ada ikut dibuat
this.addVertex(v2);
this.adjacency.get(v1).push(v2); // graph tanpa arah:
this.adjacency.get(v2).push(v1); // catat di kedua ujung
}
}
const g = new Graph();
g.addEdge("Jakarta", "Bandung");
g.addEdge("Jakarta", "Surabaya");
console.log(g.adjacency.get("Jakarta")); // ["Bandung", "Surabaya"]
console.log(g.adjacency.get("Bandung")); // ["Jakarta"]
Mapmenyimpan pasangan key dan value. Di sini key-nya node, value-nya array tetangga.addVertexcuma membuat array kosong kalau node-nya belum ada, supaya tetangga yang sudah tercatat gak terhapus.addEdgememanggiladdVertexdulu untuk kedua node, lalupushke dua array. Urutan tetangga mengikuti urutanaddEdgedipanggil.
Adjacency list atau adjacency matrix?
Cara lain menyimpan graph adalah adjacency matrix: tabel (array 2D) berukuran jumlah node kali jumlah node, berisi 1 kalau ada edge dan 0 kalau gak. Mengecek "ada edge antara A dan B?" langsung, O(1), tapi tabelnya selalu penuh, walaupun edge-nya sedikit: 1.000 node butuh 1.000.000 kotak. Adjacency list cuma menyimpan edge yang memang ada, jadi jauh lebih hemat untuk graph yang edge-nya sedikit (sparse). Pilih list, kecuali hampir semua node saling tersambung.
⚠️ Jebakan yang sering ketemu
- Lupa ujung kedua. Di graph tanpa arah,
addEdgeharuspushke dua array. Kalau cuma satu, node di ujung lainnya kelihatan gak punya tetangga. addVertexmenimpa.this.adjacency.set(v, [])tanpa cekhasmenghapus tetangga yang sudah tercatat.- Node yang belum terdaftar.
this.adjacency.get(v)untuk node yang belum ada hasilnyaundefined, dan.pushlangsung error. PanggiladdVertexdi dalamaddEdge. - Cycle bikin penelusuran gak berhenti. Waktu menelusuri graph (lesson berikutnya), catat node yang sudah dikunjungi, karena cycle bisa membawamu balik ke tempat yang sama terus-menerus.
TL;DR: Graph adalah node yang disambung edge. Tetangga sebuah node adalah node yang tersambung langsung, dan degree adalah jumlah tetangganya. Adjacency list menyimpan array tetangga untuk tiap node, misalnya di Map. Graph tanpa arah mencatat tiap edge di kedua ujungnya; graph berarah cuma di node asalnya. Adjacency list hemat untuk graph yang edge-nya sedikit, adjacency matrix selalu butuh node kali node kotak.
