Graph Representations: Adjacency List vs Adjacency Matrix

To run any algorithm on a graph you first have to store it in memory. The two standard representations are the adjacency list (each vertex keeps a list of its neighbors) and the adjacency matrix (a V × V grid where cell [u][v] says whether an edge exists). Which you pick depends on whether the graph is sparse or dense and which operations you need to be fast.

Adjacency list

An adjacency list stores, for each vertex, a list of the vertices it connects to. It uses O(V + E) space — proportional to the actual number of edges — which makes it the default for most problems because real-world graphs are sparse.

std::vector<std::vector<int>> buildAdjList(int V,
        const std::vector<std::pair<int,int>>& edges, bool directed) {
    std::vector<std::vector<int>> adj(V);
    for (auto [u, v] : edges) {
        adj[u].push_back(v);
        if (!directed) adj[v].push_back(u);
    }
    return adj;
}

List<List<Integer>> buildAdjList(int V, int[][] edges, boolean directed) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        if (!directed) adj.get(e[1]).add(e[0]);
    }
    return adj;
}

function buildAdjList(V, edges, directed) {
  const adj = Array.from({ length: V }, () => []);
  for (const [u, v] of edges) {
    adj[u].push(v);
    if (!directed) adj[v].push(u);
  }
  return adj;
}

def build_adj_list(V, edges, directed=False):
    adj = [[] for _ in range(V)]
    for u, v in edges:
        adj[u].append(v)
        if not directed:
            adj[v].append(u)
    return adj

Tip: For a weighted graph, store pairs (neighbor, weight) in each list instead of bare neighbor ids. Most pages in this section use that form.

Adjacency matrix

An adjacency matrix is a V × V table; matrix[u][v] = 1 (or the edge weight) means an edge exists. Lookups “is there an edge u → v?” are O(1), but it always uses O(V²) space even if the graph has few edges — so it’s best for dense graphs or when you constantly test edge existence.

std::vector<std::vector<int>> buildAdjMatrix(int V,
        const std::vector<std::pair<int,int>>& edges, bool directed) {
    std::vector<std::vector<int>> m(V, std::vector<int>(V, 0));
    for (auto [u, v] : edges) {
        m[u][v] = 1;
        if (!directed) m[v][u] = 1;
    }
    return m;
}

int[][] buildAdjMatrix(int V, int[][] edges, boolean directed) {
    int[][] m = new int[V][V];
    for (int[] e : edges) {
        m[e[0]][e[1]] = 1;
        if (!directed) m[e[1]][e[0]] = 1;
    }
    return m;
}

function buildAdjMatrix(V, edges, directed) {
  const m = Array.from({ length: V }, () => new Array(V).fill(0));
  for (const [u, v] of edges) {
    m[u][v] = 1;
    if (!directed) m[v][u] = 1;
  }
  return m;
}

def build_adj_matrix(V, edges, directed=False):
    m = [[0] * V for _ in range(V)]
    for u, v in edges:
        m[u][v] = 1
        if not directed:
            m[v][u] = 1
    return m

Comparing the two

Operation                 Adjacency List    Adjacency Matrix
Space                      O(V + E)          O(V^2)
Add edge                   O(1)              O(1)
Check edge u-v exists      O(degree(u))      O(1)
Iterate neighbors of u     O(degree(u))      O(V)
Best for                   sparse graphs     dense graphs

Which should you use?

Adjacency list — the default. Sparse graphs, traversals like BFS and DFS, and shortest paths such as Dijkstra all run in O(V + E) with a list.
Adjacency matrix — choose it for dense graphs, for O(1) edge tests, or for algorithms naturally expressed on a grid like Floyd-Warshall.

Going deeper: A third form, the edge list (just a flat list of (u, v, w) tuples), is the most compact and is exactly what Bellman-Ford and Kruskal’s MST iterate over.

Next, traverse your graph with breadth-first search.