How do you represent a graph?

The representation affects both time and memory. An adjacency list uses O(V + E) space and lets you iterate over a vertex's neighbours efficiently. A matrix uses O(V^2) space regardless of edge count, but edge existence is a constant-time lookup.

const graph = new Map([
  ["A", ["B", "C"]],
  ["B", ["A", "D"]],
  ["C", ["A"]],
  ["D", ["B"]],
]);

Choosing a representation

• Adjacency list: O(V + E) space, fast neighbour iteration, common for BFS and DFS
• Adjacency matrix: O(V^2) space, O(1) edge lookup, useful for dense graphs
• Edge list: O(E) space, convenient for Kruskal's algorithm
• Weighted graphs store a weight alongside each neighbour
• Directed graphs store only outgoing edges unless you also need reverse traversal

const weighted = new Map([
  ["A", [["B", 4], ["C", 1]]],
  ["B", [["A", 4], ["D", 2]]],
  ["C", [["A", 1], ["D", 5]]],
  ["D", [["B", 2], ["C", 5]]],
]);