Topics › Graphs › Learning

Graph Representation | C++

Easy TUF ID 2870 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

What this covers

An edge list is enough to define a graph, but it is a poor structure for algorithms: answering “who are the neighbours of u?” means scanning every edge. Every traversal asks that question once per vertex, so we need a representation that answers it quickly. There are two standard choices, the adjacency matrix and the adjacency list, and this article builds both from the usual input format.

The input format

Graph problems in competitive programming usually start like this:

5 6        <- n vertices, m edges
1 2
1 3
2 4
3 4
2 5
4 5

The first line gives n and m, then m lines each give one edge. Vertices are numbered 1..n. Unless the problem says otherwise, the graph is undirected, so 1 2 means 1 and 2 are neighbours of each other. The Java tests pass the edges as an int[][] with rows {u, v}, which is exactly what reading those m lines would produce. This is the example graph used below:

1 ----- 2 ----- 5
|       |       |
|       |       |
3 ----- 4 ------+

Adjacency matrix

Allocate an (n + 1) x (n + 1) table of zeros and set mat[u][v] = mat[v][u] = 1 for every edge. Size n + 1, not n, so that vertex n has a row; row and column 0 are simply unused because the vertices start at 1. In C++:

vector<vector<int>> adj(n + 1, vector<int>(n + 1, 0));
for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u][v] = 1;
    adj[v][u] = 1;
}

The Java method does the same with an int[][], which Java initialises to zeros for free:

static int[][] adjacencyMatrix(int n, int[][] edges) {
    int[][] mat = new int[n + 1][n + 1];                 // row and column 0 unused: vertices are 1-based
    for (int[] e : edges) {
        mat[e[0]][e[1]] = 1;
        mat[e[1]][e[0]] = 1;                             // undirected: the matrix is symmetric
    }
    return mat;
}

Row 2 of the example matrix is [0, 1, 0, 0, 1, 1]: vertex 2 is joined to 1, 4 and 5. Because every undirected edge sets two cells, the matrix is symmetric, mat[u][v] == mat[v][u], and counting the non-zero cells and halving gives E:

static List<Integer> neighboursFromMatrix(int[][] mat, int u) {
    List<Integer> out = new ArrayList<>();
    for (int v = 1; v < mat.length; v++) {
        if (mat[u][v] != 0) out.add(v);
    }
    return out;
}

static int edgesInMatrix(int[][] mat) {
    int cells = 0;
    for (int[] row : mat) {
        for (int x : row) if (x != 0) cells++;
    }
    return cells / 2;
}

The matrix answers “is there an edge between u and v?” in O(1), which is its great strength. Its weakness is space and neighbour enumeration. It always uses (n + 1)^2 cells, regardless of how many edges exist, and listing the neighbours of u means scanning a whole row, O(n), even when u has a single neighbour. For n = 10^5 the matrix would need 10^10 cells, about 40 GB of ints. Use it only when n is small (roughly up to a few thousand) or the graph is dense.

Adjacency list

Instead of a full row per vertex, store for each vertex only the list of its neighbours. In C++ the classic form is an array of vectors:

vector<int> adj[n + 1];           // as in the lecture; vector<vector<int>> adj(n + 1) is the portable form
for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    adj[v].push_back(u);
}

The Java equivalent is a List of List<Integer>, with one inner list created per vertex before any edge is added:

static List<List<Integer>> adjacencyList(int n, int[][] edges) {
    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]);
    }
    return adj;
}

For the example graph:

Each neighbour list is in input order, not sorted. Each undirected edge appears twice, once in each endpoint’s list, so the total number of stored entries is 2E, here 12. That is the space complexity, O(V + E): one (possibly empty) list per vertex plus 2E entries. Listing the neighbours of u takes O(deg(u)), so a full traversal that visits each vertex once and each list once costs O(V + E). That is why the adjacency list is the default for almost every graph problem. The price is that “is v a neighbour of u?” now costs O(deg(u)) instead of O(1).

static int storedEntries(List<? extends List<?>> adj) {
    int total = 0;
    for (List<?> list : adj) total += list.size();
    return total;
}

static int[][] listToMatrix(List<List<Integer>> adj) {
    int size = adj.size();
    int[][] mat = new int[size][size];
    for (int u = 0; u < size; u++) {
        for (int v : adj.get(u)) mat[u][v] = 1;
    }
    return mat;
}

listToMatrix is a sanity check used in the tests: rebuilding the matrix from the list gives exactly the matrix built directly, so the two structures describe the same graph.

Directed graphs

For a directed graph only the arrow u -> v is recorded. In C++ the second push_back disappears; in the matrix only adj[u][v] = 1 is set and the matrix stops being symmetric.

static List<List<Integer>> directedList(int n, int[][] edges) {
    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]);
    return adj;
}

With the same six input lines read as arrows, vertex 2’s list becomes [4, 5] and vertex 5’s list is empty. The list stores E entries rather than 2E.

Weighted graphs

When each input line is u v w, the matrix simply stores w instead of 1:

static int[][] weightedMatrix(int n, int[][] wEdges) {
    int[][] mat = new int[n + 1][n + 1];
    for (int[] e : wEdges) {
        mat[e[0]][e[1]] = e[2];
        mat[e[1]][e[0]] = e[2];
    }
    return mat;
}

This only works if 0 can still mean “no edge”. If weights can be zero or negative, fill the matrix with a sentinel such as Integer.MAX_VALUE first, or keep a separate boolean matrix.

In the list each entry must hold two numbers. C++ uses vector<pair<int, int>> adj[n + 1] and pushes {v, w}. Java has no built-in pair type, so a two-element int[] plays that role:

static List<List<int[]>> weightedList(int n, int[][] wEdges) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
    for (int[] e : wEdges) {
        adj.get(e[0]).add(new int[]{e[1], e[2]});
        adj.get(e[1]).add(new int[]{e[0], e[2]});
    }
    return adj;
}

For edges 1-2 (2), 1-3 (3), 2-4 (1), 3-4 (6), vertex 4’s list is [{2, 1}, {3, 6}]: neighbour 2 at weight 1 and neighbour 3 at weight 6.

Matrix or list?

The tests make the space difference concrete with a path on 100000 vertices: the list stores 199998 entries, while the matrix would need over 10^10 cells.

Edge cases and pitfalls

• Size n + 1 for 1-based input. Allocating n rows and then indexing vertex n is the classic off-by-one. For 0-based input, size n.
• Undirected means two insertions. Forgetting adj[v].push_back(u) silently turns the graph into a directed one, and traversals then miss vertices.
• Isolated vertices. A vertex with no edges still has an (empty) list. Creating lists lazily only for vertices that appear in edges leaves holes.
• Zero weights in a matrix. 0 doubles as “no edge”; pick a sentinel if zero is a legal weight.
• Self-loops. In a list a self-loop {u, u} stores u twice in its own list; in a matrix it sets one diagonal cell, so “non-zero cells / 2” no longer counts edges.
• Stack versus heap in C++. A fixed array such as int adj[N][N] declared inside a function lives on the stack and crashes for large N; declare it globally or use vector.

Related problems

• Introduction to Graph defines vertices, edges, degree, paths and cycles on plain edge lists.

• [Graph Representation

  Java](/dsa-java-articles/p/2871.html) covers ArrayList of ArrayList, arrays of lists, compact arrays and maps.

• Traversal Techniques runs BFS over the adjacency list built here.
• Number of provinces gives its input as an adjacency matrix.