Lesson 20.2 · Graph Fundamentals

Storing a Graph: Edge List, Matrix, Adjacency List

Problems usually hand you an edge list; you almost always convert it to an adjacency list, which uses O(V + E) memory and lists each node's neighbours directly.

14 min

Think of it like this

Three ways to record friendships at a school: a list of pairs on paper (edge list), a giant table with a tick for every pair (matrix), or each student's own contact list (adjacency list). The contact lists are what you use when you actually want to call someone's friends.

1.Three representations

Edge list [[u, v], …]: how inputs arrive. Good for sorting edges (Kruskal), bad for "who are u's neighbours?" (O(E) scan).

Adjacency matrix boolean[n][n]: O(1) to test whether u and v are connected, but O(V²) memory and O(V) to list neighbours. Use it for small dense graphs.

Adjacency list List<List<Integer>>: each node keeps its neighbours. O(V + E) memory and neighbours are listed in O(degree). This is the default for BFS, DFS and everything else. For an undirected edge, add it in both directions; for weights, store int[]{neighbour, weight}.

Main.java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}};
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);   // undirected: both directions
        }
        for (int i = 0; i < n; i++) System.out.println(i + " -> " + adj.get(i));
        System.out.println("degree of 3 = " + adj.get(3).size());
    }
}

Output

0 -> [1, 2]
1 -> [0, 3]
2 -> [0, 3]
3 -> [1, 2, 4]
4 -> [3]
degree of 3 = 3

Remember

Convert edge lists to adjacency lists first.
Undirected edges go in twice.
Matrix only for small or dense graphs.

Common mistakes

Building an n × n matrix for n = 10⁵ (10¹⁰ cells).
Adding undirected edges in one direction only.

Command Palette

Storing a Graph: Edge List, Matrix, Adjacency List

1.Three representations