Gyaan

Graph Representations

beginner graph adjacency-list adjacency-matrix data-structure

A graph is just a collection of nodes (also called vertices) connected by edges. That’s it. Think of a social network: people are nodes, friendships are edges.

Graphs are everywhere in interviews. Shortest path, connected components, dependency resolution — all graph problems. Before we can solve any of them, we need to know how to represent a graph in code.

Types of Graphs

Undirected Graph
A ————— B ————— C
Edges go both ways. A↔B means B↔A too. Like friendships.
Directed Graph (Digraph)
A ——→ B ——→ C
Edges have direction. A→B doesn't mean B→A. Like Twitter follows.
Weighted Graph
A —5— B —3— C
Edges have costs/weights. Like distances between cities.

Representation 1: Adjacency List (Most Common)

This is what we’ll use 90% of the time in interviews. For each node, we store a list of its neighbors.

In simple language, it’s like a phone book. Each person’s entry lists who they’re connected to.

// Build adjacency list from edge list (undirected)
function buildGraph(edges, n) {
  const graph = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    graph[u].push(v); // u connects to v
    graph[v].push(u); // v connects to u (undirected)
  }
  return graph;
}
// edges = [[0,1], [0,2], [1,3]]
// graph = [[1,2], [0,3], [0], [1]]
# Build adjacency list from edge list (undirected)
from collections import defaultdict

def build_graph(edges, n):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)  # u connects to v
        graph[v].append(u)  # v connects to u (undirected)
    return graph
# edges = [[0,1], [0,2], [1,3]]
# graph = {0: [1,2], 1: [0,3], 2: [0], 3: [1]}
// Build adjacency list from edge list (undirected)
List<List<Integer>> buildGraph(int[][] edges, int n) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] e : edges) {
        graph.get(e[0]).add(e[1]); // u connects to v
        graph.get(e[1]).add(e[0]); // v connects to u
    }
    return graph;
}

For a directed graph, we just skip the second line — only add u → v, not v → u.

For a weighted graph, we store [neighbor, weight] pairs instead of just neighbors:

// Weighted adjacency list
function buildWeightedGraph(edges) {
  const graph = new Map();
  for (const [u, v, weight] of edges) {
    if (!graph.has(u)) graph.set(u, []);
    if (!graph.has(v)) graph.set(v, []);
    graph.get(u).push([v, weight]);
    graph.get(v).push([u, weight]); // skip for directed
  }
  return graph;
}
# Weighted adjacency list
def build_weighted_graph(edges):
    graph = defaultdict(list)
    for u, v, weight in edges:
        graph[u].append((v, weight))
        graph[v].append((u, weight))  # skip for directed
    return graph
// Weighted adjacency list — store int[] {neighbor, weight}
Map<Integer, List<int[]>> buildWeightedGraph(int[][] edges) {
    Map<Integer, List<int[]>> graph = new HashMap<>();
    for (int[] e : edges) {
        graph.computeIfAbsent(e[0], k -> new ArrayList<>()).add(new int[]{e[1], e[2]});
        graph.computeIfAbsent(e[1], k -> new ArrayList<>()).add(new int[]{e[0], e[2]});
    }
    return graph;
}

Representation 2: Adjacency Matrix

A 2D array where matrix[i][j] = 1 means there’s an edge from node i to node j. For weighted graphs, store the weight instead of 1.

// Build adjacency matrix (undirected)
function buildMatrix(edges, n) {
  const matrix = Array.from({ length: n }, () => Array(n).fill(0));
  for (const [u, v] of edges) {
    matrix[u][v] = 1;
    matrix[v][u] = 1; // undirected
  }
  return matrix;
}
# Build adjacency matrix (undirected)
def build_matrix(edges, n):
    matrix = [[0] * n for _ in range(n)]
    for u, v in edges:
        matrix[u][v] = 1
        matrix[v][u] = 1  # undirected
    return matrix
// Build adjacency matrix (undirected)
int[][] buildMatrix(int[][] edges, int n) {
    int[][] matrix = new int[n][n];
    for (int[] e : edges) {
        matrix[e[0]][e[1]] = 1;
        matrix[e[1]][e[0]] = 1; // undirected
    }
    return matrix;
}

When to Use Which?

Adjacency List
Adjacency Matrix
Space
O(V + E)
O(V²)
Check edge exists
O(neighbors)
O(1)
Get all neighbors
O(neighbors)
O(V)
Best for
Sparse graphs (most interview problems)
Dense graphs, quick edge lookup

Interview rule of thumb: Use adjacency list unless the problem specifically needs O(1) edge lookups. Most graph problems give us sparse graphs (way fewer edges than V²), so adjacency list saves space and is easier to traverse.

Common Input Format: Edge List

Many LeetCode problems give us edges as [[0,1], [1,2], [2,0]] plus the number of nodes n. Our first step is always converting this to an adjacency list. That’s the “build the graph” step before we do BFS/DFS.

Sometimes we get a different format — like a grid (2D array) where each cell is a node. We’ll cover grid traversal in the BFS/DFS topic.

Key Terminology

  • Degree — number of edges connected to a node. In directed graphs: in-degree (incoming edges) and out-degree (outgoing edges).
  • Path — sequence of nodes where each consecutive pair has an edge.
  • Cycle — a path that starts and ends at the same node.
  • Connected — there’s a path between every pair of nodes (undirected graphs).
  • DAG — Directed Acyclic Graph. A directed graph with no cycles. Super important for topological sort.

Graphs are the foundation for everything coming next — BFS, DFS, shortest paths, topological sort. Get comfortable building adjacency lists from edge lists, because we’ll be doing it in every graph problem.

References