Graph Representation

🧠 Mental Model

The single question that drives the choice: "What do I ask most often?"

• "Is there an edge between u and v?" → matrix (O(1) lookup).
• "Who are u's neighbors?" → adjacency list (iterate only real edges).
• "Give me all edges to sort them" → edge list (Kruskal's loves this).

⚙️ The Three Representations

1. Adjacency List (the interview default)

Each node stores a list of its neighbors. For n nodes you keep n lists. This is what you'll use in ~90% of interview problems because most graphs are sparse (edges ≪ n²).

2. Adjacency Matrix

An n × n grid where matrix[u][v] = 1 (or the weight) if an edge exists. Instant edge lookups, but costs O(n²) space even if the graph has 3 edges. Great for dense graphs or Floyd-Warshall (Week 2).

3. Edge List

Just a list of (u, v, weight) triples. Minimal, and perfect when the algorithm processes edges directly (Kruskal's, Bellman-Ford).

Directed vs Undirected · Weighted vs Unweighted

• Undirected: add the edge both ways (u→v and v→u). Forgetting this is the #1 beginner bug.
• Directed: add only u→v.
• Weighted: store the weight alongside the neighbor (e.g. int[]{v, w} or a small class).

📊 Complexity & When to Use

💻 Reference Implementation (Java)

A flexible Graph class backed by an adjacency list, supporting directed/undirected and weighted edges.

import java.util.*;

/** Weighted adjacency-list graph. Set weighted=false to ignore weights. */
public class Graph {
    private final int n;
    private final boolean directed;
    private final List<int[]>[] adj;   // adj[u] = list of {neighbor, weight}

    public Graph(int n, boolean directed) {
        this.n = n;
        this.directed = directed;
        adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
    }

    public void addEdge(int u, int v, int w) {
        adj[u].add(new int[]{v, w});
        if (!directed) adj[v].add(new int[]{u, w}); // undirected → both ways
    }

    public void addEdge(int u, int v) { addEdge(u, v, 1); } // unweighted default

    public List<int[]> neighbors(int u) { return adj[u]; }

    public int size() { return n; }
}

// --- Adjacency matrix, when you need O(1) edge lookups ---
int[][] matrix = new int[n][n];
matrix[u][v] = w;                 // directed
// matrix[v][u] = w;             // add this line for undirected

⚠️ Common Pitfalls

🎯 Problems