Graph Representations

Graph Representations

Alright, so you understand what a graph is. But how do we actually store one in code? There are two main ways, and each has its own strengths. Let's break them down so you can pick the right one.

The choice of representation can make or break your algorithm's performance. It's like choosing between a phonebook (organized by name) and a map (organized by location) — both have their use cases.

Adjacency Matrix

An adjacency matrix is a 2D array where each cell [i][j] tells you if there's an edge from vertex i to vertex j. It's like a seating chart at a party — rows are people, columns are people, and a 1 means they're connected.

Checking if two vertices are connected is super fast — O(1) time. But it uses a lot of memory, especially for sparse graphs where most vertices aren't connected to each other.

const matrix = [
  [0, 1, 1, 0],
  [1, 0, 0, 1],
  [1, 0, 0, 1],
  [0, 1, 1, 0]
];

Adjacency List

An adjacency list stores each vertex and its list of neighbors. Think of it like a contact list on your phone — each person has a list of people they're connected to. Much more space-efficient!

This is the go-to representation for most graph problems. It's perfect when your graph is sparse (most vertices aren't connected) and you want to iterate over neighbors efficiently.

const adjacencyList = {
  A: ["B", "C"],
  B: ["A", "D"],
  C: ["A", "D"],
  D: ["B", "C"]
};

When to Use Each

Use adjacency matrix when: You need to check edge existence frequently, the graph is dense (most vertices are connected), or you're working with small graphs where memory isn't a concern.

Use adjacency list when: The graph is sparse, you need to iterate over neighbors, or you're working with large graphs where memory matters. Most real-world graphs are sparse, so adjacency lists are usually the better choice.