Sebelum membahas algoritma graph (BFS, DFS, Dijkstra), kita perlu tahu bagaimana cara menyimpan graph di dalam kode. Ada dua cara utama: adjacency list dan adjacency matrix.

Pilihan representasi menentukan berapa cepat kamu bisa cek tetangga, tambah edge, dan seberapa boros memori.

Adjacency List

Setiap node punya list berisi tetangga-tetangganya. Cocok untuk sparse graph (sedikit edge).

// Graph: 0—1, 0—2, 1—2, 2—3
const adjList = {
  0: [1, 2],
  1: [0, 2],
  2: [0, 1, 3],
  3: [2],
};

// Cek tetangga node 2?
console.log(adjList[2]); // [0, 1, 3]

// Iterasi semua edge dari node 0
for (const neighbor of adjList[0]) {
  console.log(`0 → ${neighbor}`);
}

Variasi untuk array-based node (0..n-1):

const adj = Array.from({ length: n }, () => []);
adj[0].push(1);
adj[1].push(0); // undirected: kedua arah

Adjacency Matrix

Matriks 2D matrix[i][j] = 1 jika ada edge i → j. Cocok untuk dense graph (banyak edge) atau ketika kamu sering cek "apakah ada edge antara i dan j?".

// Graph yang sama (4 node)
const matrix = [
  [0, 1, 1, 0], // node 0 → 1, 2
  [1, 0, 1, 0], // node 1 → 0, 2
  [1, 1, 0, 1], // node 2 → 0, 1, 3
  [0, 0, 1, 0], // node 3 → 2
];

// Cek edge 0—2?
console.log(matrix[0][2]); // 1 (ada edge)

Weighted Edges

Untuk graph berbobot (misal jarak antar kota), simpan bobotnya di list atau matrix.

// Adjacency list dengan bobot
const weighted = {
  A: [["B", 5], ["C", 3]],
  B: [["A", 5], ["C", 2]],
  C: [["A", 3], ["B", 2]],
};

// Matrix dengan bobot — Infinity jika tidak ada edge
const INF = Infinity;
const mat = [
  [0,   5,   3],
  [5,   0,   2],
  [3,   2,   0],
];

Directed vs Undirected

• Undirected (teman di media sosial): jika A terhubung ke B, B juga terhubung ke A. Di adjacency list, push kedua arah. Matrix akan simetris.
• Directed (follower Twitter): A follow B, tidak berarti B follow A. Push hanya satu arah.

// Directed
adj[A].push(B); // A → B saja

// Undirected
adj[A].push(B);
adj[B].push(A); // dua arah

Trade-off

Panduan memilih:

• Sparse (E << V²) → adjacency list (lebih hemat memori)
• Dense (E ≈ V²) → adjacency matrix (akses O(1))
• Sering cek edge spesifik → matrix
• Sering iterasi tetangga → list

Tip: Sebagian besar kasus nyata (social network, web link, peta kota) adalah sparse graph. Default pakai adjacency list kecuali ada alasan kuat.

🎭 Analogi sehari-hari: Cara nyimpen daftar teman.

• Adjacency List: kayak buku catatan — tiap nama punya halaman dengan list temannya. Hemat kalau temennya sedikit
• Adjacency Matrix: spreadsheet 100×100 cell — tiap cell tandai "temen ya/tidak". Cepat cek "Si A temen sama si B?" tapi boros kalau temennya cuma 5 dari 100

💡 Sparse vs Dense: Graph dunia nyata hampir selalu sparse. Social network rata-rata punya ~150 teman dari milyaran user. Web pages link ke ratusan, bukan milyaran. Peta kota punya jalan ke beberapa tetangga, bukan ke semua. Default: adjacency list.

⚠️ Jebakan umum:

• Pakai matrix untuk graph besar sparse = OOM. n=100rb butuh 10 milyar cell, ~80GB
• Lupa undirected = push 2 arah di adjacency list
• Lupa Infinity untuk weighted matrix = 0 ambigu (no edge atau weight 0?)
• Modify saat iterate adj list = bug halus

🎯 Decision tree:

• |V| ≤ 1000 + dense → matrix (simpel, cepat)
• |V| besar + sparse → adjacency list (default 99% kasus)
• Weighted dense + Floyd-Warshall → matrix
• Edge query frequent → matrix (O(1))
• Iterate neighbors frequent → list (O(deg))

🧪 Tebakan cepat: Social network 1jt user, rata-rata 200 teman. Pakai matrix? 1 trilyun cell = 8 TB. Pakai list? 200jt entries = 1.6 GB. Selisih 5000x.

TL;DR: Adjacency List untuk sparse (default), Adjacency Matrix untuk dense atau frequent edge query. Default 99% pakai list. Hindari matrix untuk graph besar.