Graph adalah kumpulan node (vertex) yang dihubungkan oleh edge (sisi). Tidak seperti tree, graph bisa punya cycle dan node bisa terhubung ke siapa saja.

Jenis Graph:

Representasi di kode:

// Adjacency List — paling umum
class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  // Undirected edge
  addEdge(v1, v2) {
    this.adjacencyList.get(v1).push(v2);
    this.adjacencyList.get(v2).push(v1);
  }
}

const g = new Graph();
["Jakarta", "Bandung", "Surabaya", "Yogya"].forEach(v => g.addVertex(v));
g.addEdge("Jakarta", "Bandung");
g.addEdge("Jakarta", "Surabaya");
g.addEdge("Bandung", "Yogya");
g.addEdge("Surabaya", "Yogya");

// Jakarta: [Bandung, Surabaya]
// Bandung: [Jakarta, Yogya]
// Surabaya: [Jakarta, Yogya]
// Yogya: [Bandung, Surabaya]

Kegunaan nyata:

• Peta & navigasi — kota = vertex, jalan = edge
• Social network — orang = vertex, pertemanan = edge
• Internet — router = vertex, koneksi = edge
• Dependency management — package = vertex, dependency = edge

🎭 Analogi sehari-hari: Graph = peta hubungan teman di kampus. Setiap orang = vertex. Garis "kenalan dengan" = edge. Bedanya:

• Directed = "Budi follow Ani di IG, tapi Ani gak follow balik"
• Undirected = "Budi & Ani saling chat" (dua arah)
• Weighted = "Budi → Ani jaraknya 200m" (edge punya bobot)

Tree = kasus khusus graph (no cycle, satu root). Graph lebih bebas.

💡 Adjacency List vs Matrix:

• List: Map<vertex, [tetangga]>. Hemat memori untuk graph sparse (sedikit edge). O(V+E) space
• Matrix: array 2D, m[i][j] = 1 kalau ada edge. Cepat cek "ada edge?" O(1) tapi boros memori O(V²)

Default pilih List kecuali graph dense (>50% kemungkinan edge ada).

⚠️ Jebakan umum:

• Lupa addEdge dua arah untuk undirected graph = jalur cuma jalan satu arah
• Cycle detection = wajib pakai visited set, lupa = infinite loop
• Self-loop (vertex ke diri sendiri) = beberapa algoritma gak handle, validasi dulu
• Multi-edge (2 edge antar vertex sama) = perlu desain khusus, default representation tidak preserve

🎯 Kapan butuh Graph (bukan Tree)?

• Cycle bisa ada (sosial network, dependency dengan circular ref)
• Banyak parent (anak punya 2 ortu = bukan tree)
• Hubungan many-to-many

TL;DR: Graph = vertex + edge, lebih fleksibel dari tree. Adjacency List paling umum. Fondasi navigasi, social network, dan dependency management.