Graph adalah cara menggambarkan hal-hal yang saling tersambung. Tiap hal disebut node (titik), dan sambungan antara dua node disebut edge (garis). Contoh paling gampang: peta. Kotanya node, jalannya edge. Lesson ini membahas cara menyimpan graph di kode, supaya bisa dipakai algoritma seperti BFS, DFS, dan Dijkstra.
🧪 Tebakan cepat: ada 10.000 kota dan 50.000 jalan. Kalau disimpan sebagai matrix, butuh berapa sel: 50.000, 100.000, atau 100 juta? Tebak dulu, jawabannya ada di bagian "List atau matrix?".
Adjacency list: tiap kota menyimpan tetangganya
Ada empat kota: A, B, C, D. Jalannya A-B, B-C, C-D, dan D-A, membentuk kotak. Semua jalan dua arah, jadi graph ini tak berarah (undirected): kalau A tersambung ke B, B juga tersambung ke A. Dua kota yang disambung satu jalan disebut tetangga. Kita catat jalannya satu per satu:
| Jalan | Yang dicatat |
|---|---|
| A-B | B masuk daftar A, A masuk daftar B |
| A-D | D masuk daftar A, A masuk daftar D |
| B-C | C masuk daftar B, B masuk daftar C |
| C-D | D masuk daftar C, C masuk daftar D |
Hasilnya, ditulis sebagai object:
const graph = {
A: ["B", "D"],
B: ["A", "C"],
C: ["B", "D"],
D: ["A", "C"],
};
console.log(graph.A); // ["B", "D"]
console.log(graph.A.includes("C")); // false
- Ini adjacency list (daftar tetangga): tiap kunci adalah satu kota, isinya array berisi tetangganya.
graph.Alangsung memberi semua tetangga A.graph.A.includes("C")mengecek "A tersambung langsung ke C?" dengan menyisir daftar A satu per satu. Jawabannyafalse: dari A ke C harus lewat B atau D.- Tiap jalan dicatat dua kali, sekali di tiap ujungnya, karena graph-nya tak berarah.
Adjacency matrix: tabel sambungan
const nodes = ["A", "B", "C", "D"];
const matrix = [
[0, 1, 0, 1], // A
[1, 0, 1, 0], // B
[0, 1, 0, 1], // C
[1, 0, 1, 0], // D
];
console.log(matrix[0][1]); // 1: A tersambung ke B
console.log(matrix[0][2]); // 0: A gak tersambung ke C
Adjacency matrix adalah tabel V × V, dengan V jumlah node. Baris dan kolom memakai urutan nodes: A index 0, B index 1, C index 2, D index 3. matrix[i][j] bernilai 1 kalau node i dan j tersambung, 0 kalau gak. Diagonalnya (matrix[0][0], matrix[1][1], ...) selalu 0, karena gak ada jalan dari kota ke dirinya sendiri. Di graph tak berarah, matrix[i][j] selalu sama dengan matrix[j][i]: matrix-nya simetris.
Graph berarah (directed) punya sambungan satu arah, kayak follow di media sosial: A follow B belum tentu B follow A. Di list, catat satu arah saja. Di matrix, cuma matrix[a][b] yang jadi 1, jadi matrix-nya gak simetris lagi. Kalau jalannya punya panjang (bobot), list menyimpan pasangan [tetangga, bobot], misalnya A: [["B", 4], ["D", 7]].
Node sebagai angka
Sering node langsung diberi nomor 0 sampai n - 1. Adjacency list-nya jadi array berisi array, dengan index luar sebagai nomor node: [[1, 2], [0, 2], [0, 1, 3], [2]] artinya node 0 bertetangga dengan 1 dan 2, dan node 3 cuma dengan 2.
const n = 3;
const matrix = Array.from({ length: n }, () => new Array(n).fill(0));
matrix[0][2] = 1; // jalan 0-2...
matrix[2][0] = 1; // ...dicatat di dua sisi
console.log(matrix[0].join(",")); // 0,0,1
const tetangga = [];
for (let v = 0; v < n; v++) {
if (matrix[2][v] === 1) tetangga.push(v);
}
console.log(tetangga); // [0]
Array.from({ length: n }, () => new Array(n).fill(0))bikin n baris, tiap baris array baru berisi n angka 0.- List ke matrix: untuk tiap node
udan tiap tetangganyav, isimatrix[u][v]danmatrix[v][u]dengan 1. - Matrix ke list: untuk tiap baris, kumpulkan index kolom yang bernilai 1, dari kiri ke kanan, jadi urutannya otomatis dari kecil ke besar.
join(",")menggabungkan isi array jadi teks:[0, 0, 1]jadi0,0,1.
List atau matrix?
Big-O menggambarkan berapa kerja yang dibutuhkan saat data membesar. O(1) artinya kerjanya tetap, berapa pun jumlah node. O(V) artinya node dua kali lipat, kerjanya kira-kira dua kali lipat. V adalah jumlah node, E jumlah edge.
| Pekerjaan | Adjacency list | Adjacency matrix |
|---|---|---|
| Cek "i tersambung ke j?" | sisir daftar tetangga i | O(1), langsung matrix[i][j] |
| Ambil semua tetangga i | langsung daftarnya | sisir satu baris, O(V) |
| Memori | O(V + E): satu daftar per node, tiap edge dicatat 2 kali | O(V²), alias selalu V × V sel |
Kebanyakan graph nyata itu sparse (jarang): edge-nya sedikit dibanding semua pasangan yang mungkin. 10.000 kota dengan 50.000 jalan butuh matrix 10.000 × 10.000 = 100 juta sel, sedangkan list cuma sekitar 100.000 isi (50.000 jalan × 2). Itu jawaban tebakannya. Jadi pilihan default-nya adjacency list. Matrix cocok untuk graph kecil yang hampir semua pasangannya tersambung, atau kalau kamu sering bertanya "i dan j tersambung gak?".
⚠️ Jebakan yang sering ketemu
- Lupa mencatat dua arah. Di graph tak berarah, satu jalan mengisi dua sel,
matrix[u][v]danmatrix[v][u], dan masuk ke dua daftar tetangga. new Array(n).fill(new Array(n).fill(0)). Semua baris jadi array yang sama persis, jadi mengubah satu sel ikut mengubah sel itu di semua baris. PakaiArray.fromsupaya tiap baris array baru.- 0 di matrix berbobot. Kalau sel menyimpan panjang jalan, 0 bisa berarti "gak ada jalan" atau "jalan sepanjang 0". Untuk "gak ada jalan", isi
Infinity.
TL;DR: Graph terdiri dari node (titik, misalnya kota) dan edge (sambungan, misalnya jalan). Adjacency list menyimpan daftar tetangga tiap node: hemat memori dan cepat mengambil semua tetangga, jadi pilihan default. Adjacency matrix adalah tabel V × V berisi 1 atau 0: cek satu sambungan cukup matrix[i][j], O(1), tapi selalu butuh V × V sel. Graph tak berarah dicatat di dua sisi (matrix-nya simetris), graph berarah di satu sisi. Diagonal matrix selalu 0.
