Graph Data Structure: Terms, Representations and Code

A graph is the data structure for things and the connections between them: cities joined by roads, people joined by friendships, courses joined by prerequisites. An array lines its items up in a row and a tree hangs them from one root; a graph lets any item connect to any other. That is why so many interview questions are graph problems in disguise, and why the breadth-first search and depth-first search lessons that follow this one matter so much.

A graph is a set of vertices (or nodes) and a set of edges, each joining two vertices. Problems usually number the vertices 0 to n − 1 and hand you the edges as a list of pairs. In formulas V and E stand for how many there are, so O(V + E) means work in proportion to both.

Where the vertices sit on the page means nothing: a graph is only the record of who is joined to whom.

The words every graph problem uses

Two vertices joined by an edge are neighbours, and a vertex's degree is the number of edges touching it. The sum in the figure is the handshake lemma: every edge adds 1 to the degree of each of its two ends, so the degrees always add up to 2E.

An undirected edge works both ways, like a friendship. A directed edge, 0 → 1, goes one way only, like a one-way street or "take course 0 before course 1", and each vertex then has an in-degree (edges arriving) and an out-degree (edges leaving). A weighted edge carries a number: a distance, a price, a time.

The difference decides the algorithm. "Fewest edges" is a breadth-first search question; "cheapest total weight" belongs to Dijkstra's algorithm, because a route with more edges can cost less. Degrees alone solve some problems: the judge in Find the Town Judge has in-degree n − 1 and out-degree 0.

• A path is a sequence of vertices, each joined to the next; its length counts edges. A cycle is a path that returns to its start without reusing an edge.
• A graph is connected when every vertex can reach every other; otherwise it falls apart into connected components, which is what Number of Provinces counts.
• A DAG, a directed acyclic graph, has no directed cycle. DAGs model dependencies, and every DAG has a topological order.
• A tree is a connected undirected graph with no cycles, and it always has exactly V − 1 edges.

1. Six vertices and no edges yet: six components, each a vertex on its own. Watch the count as edges arrive — each one can merge at most two pieces.
2. Edge 0–1 links {0} with {1}: 6 components become 5. Joining two separate pieces can never close a cycle, since no route linked them before.
3. Edge 3–4 links {3} with {4}: 5 components become 4.
4. Edge 1–4 links {0, 1} with {3, 4}: 4 components become 3.
5. Edge 2–5 links {2} with {5}: 3 components become 2.
6. Edge 1–2 links {0, 1, 3, 4} with {2, 5}: 2 components become 1. One component after 5 edges, V − 1, and no cycle: a tree. Fewer edges could not connect 6 vertices.
7. Edge 4–5 is one too many: 4 and 5 are already connected through 4–1–2–5, so the new edge closes a cycle. That is why a tree has exactly V − 1 edges, and exactly one path between any two of its vertices.

A graph with close to V × (V − 1) / 2 edges is dense; one with E about the size of V is sparse, and interview graphs nearly always are.

How a graph is stored

Every traversal asks one question over and over: who are the neighbours of u? The three standard layouts answer it at very different prices.

1. One graph, three layouts. The edge list keeps the 6 pairs as given; the matrix gives every ordered pair of vertices a cell, 25 in all; the adjacency list gives each vertex the list of its neighbours, 12 entries for 6 edges.
2. Who are the neighbours of 1? The edge list must read all 6 pairs to find the 3 that name 1: O(E) for one question, and a search asks it once for every vertex.
3. The matrix reads row 1, all 5 cells, and keeps the 3 that hold a 1: O(V) per vertex, however few neighbours it has.
4. The adjacency list hands over adj[1] = [0, 2, 3] directly: O(degree), exactly the work there is. That is why searches use it.
5. Is 3 joined to 4? The matrix answers with the single cell matrix[3][4], O(1); the list scans adj[3]. That is the matrix's one strength, bought with V² cells: 25 here, 10¹⁰ for V = 10⁵.

The edge list's O(E) scan is fatal in a search, which asks once per vertex: with V = 10⁵ and E = 2 × 10⁵ that is 2 × 10¹⁰ steps. The matrix's V² cells are fatal in memory: for V = 10⁵, about 40 GB. The adjacency list takes O(V + E) memory and answers in O(deg(u)), so it is the default for almost every graph problem. Building it is one pass over the edges, appending each undirected edge from both ends:

1. An edge list names the joined pairs, but finding one node's neighbours would mean scanning all 6 edges. An adjacency list gives each of the 5 nodes its own list instead, filled in a single pass over the edges.
2. Read edge 0–1: append 1 to adj[0], now [1], and 0 to adj[1], now [0]. The graph is undirected, so every edge is written twice, once from each end.
3. Read edge 0–2: append 2 to adj[0], now [1, 2], and 0 to adj[2], now [0]. 2 had no neighbours until now; appending to the end of a list is O(1), however long it is.
4. Read edge 1–2: append 2 to adj[1], now [0, 2], and 1 to adj[2], now [0, 1]. 1 and 2 were already linked through 1–0–2, so this edge closes a cycle; the lists still only record direct neighbours.
5. Read edge 1–3: append 3 to adj[1], now [0, 2, 3], and 1 to adj[3], now [1]. A list's length is its node's degree: 1 now has 3 neighbours, while 3 gets its first.
6. Read edge 2–4: append 4 to adj[2], now [0, 1, 4], and 2 to adj[4], now [2]. Only the two lists the edge names are touched, which is why the whole pass costs O(V + E).
7. Read edge 3–4: append 4 to adj[3], now [1, 4], and 3 to adj[4], now [2, 3]. This closes a second cycle, 3–1–2–4–3, and is stored exactly like any other edge.
8. All 6 edges are in, each stored twice, so the lists hold 12 entries: the degrees add up to 2E. Building took O(V + E), and now 1's neighbours are one lookup, adj[1] = [0, 2, 3], in O(degree) instead of an O(E) scan.

The operations and their cost

A traversal lists every vertex's neighbours once. On a list that costs the sum of the degrees, 2E, plus V for the vertices: O(V + E). On a matrix it reads V rows of V cells, O(V²). Reach for a matrix only for a small dense graph, an input that already is one, or many "is u joined to v?" checks, as in Maximal Network Rank.

The code

The program builds the adjacency list and prints each vertex's neighbours and degree, sorting each list because the order inside it is only the order the edges arrived in. Watch the first line of the builder: in Python [[]] * n, and in JavaScript new Array(n).fill([]), would create one list shared by every vertex.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// One list per vertex: adj[u] holds the neighbours of u.
vector<vector<int>> buildAdjacencyList(int n, const vector<vector<int>>& edges) {
    vector<vector<int>> adj(n);
    for (const vector<int>& e : edges) {
        adj[e[0]].push_back(e[1]);  // undirected: store the edge from both ends
        adj[e[1]].push_back(e[0]);
    }
    for (vector<int>& list : adj) sort(list.begin(), list.end());  // the order edges arrived in means nothing
    return adj;
}

int main() {
    int n = 5;
    vector<vector<int>> edges = {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 4}, {3, 4}};
    vector<vector<int>> adj = buildAdjacencyList(n, edges);
    int degreeSum = 0;
    for (int u = 0; u < n; u++) {
        // A vertex's degree is the length of its list.
        cout << "Vertex " << u << ": neighbours";
        for (int v : adj[u]) cout << " " << v;
        cout << ", degree " << adj[u].size() << "\n";
        degreeSum += (int)adj[u].size();
    }
    cout << "Sum of degrees: " << degreeSum << " (twice the " << edges.size() << " edges)\n";
    return 0;
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    // One list per vertex: adj.get(u) holds the neighbours of u.
    static List<List<Integer>> buildAdjacencyList(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int u = 0; u < n; u++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]); // undirected: store the edge from both ends
            adj.get(e[1]).add(e[0]);
        }
        for (List<Integer> list : adj) Collections.sort(list); // the order edges arrived in means nothing
        return adj;
    }

    public static void main(String[] args) {
        int n = 5;
        int[][] edges = {{0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 4}, {3, 4}};
        List<List<Integer>> adj = buildAdjacencyList(n, edges);
        int degreeSum = 0;
        for (int u = 0; u < n; u++) {
            // A vertex's degree is the length of its list.
            StringBuilder line = new StringBuilder("Vertex " + u + ": neighbours");
            for (int v : adj.get(u)) line.append(" ").append(v);
            line.append(", degree ").append(adj.get(u).size());
            System.out.println(line);
            degreeSum += adj.get(u).size();
        }
        System.out.println("Sum of degrees: " + degreeSum + " (twice the " + edges.length + " edges)");
    }
}

def build_adjacency_list(n, edges):
    """One list per vertex: adj[u] holds the neighbours of u."""
    adj = [[] for _ in range(n)]  # never [[]] * n, which shares one list
    for u, v in edges:
        adj[u].append(v)  # undirected: store the edge from both ends
        adj[v].append(u)
    for neighbours in adj:
        neighbours.sort()  # the order edges arrived in means nothing
    return adj


n = 5
edges = [[0, 1], [0, 2], [1, 2], [1, 3], [2, 4], [3, 4]]
adj = build_adjacency_list(n, edges)
degree_sum = 0
for u in range(n):
    # A vertex's degree is the length of its list.
    print(f"Vertex {u}: neighbours {' '.join(map(str, adj[u]))}, degree {len(adj[u])}")
    degree_sum += len(adj[u])
print(f"Sum of degrees: {degree_sum} (twice the {len(edges)} edges)")

// One list per vertex: adj[u] holds the neighbours of u.
function buildAdjacencyList(n, edges) {
  const adj = Array.from({ length: n }, () => []); // never new Array(n).fill([])
  for (const [u, v] of edges) {
    adj[u].push(v); // undirected: store the edge from both ends
    adj[v].push(u);
  }
  for (const list of adj) list.sort((a, b) => a - b); // the order edges arrived in means nothing
  return adj;
}

const n = 5;
const edges = [[0, 1], [0, 2], [1, 2], [1, 3], [2, 4], [3, 4]];
const adj = buildAdjacencyList(n, edges);
let degreeSum = 0;
for (let u = 0; u < n; u++) {
  // A vertex's degree is the length of its list.
  console.log(`Vertex ${u}: neighbours ${adj[u].join(" ")}, degree ${adj[u].length}`);
  degreeSum += adj[u].length;
}
console.log(`Sum of degrees: ${degreeSum} (twice the ${edges.length} edges)`);

Vertex 0: neighbours 1 2, degree 2
Vertex 1: neighbours 0 2 3, degree 3
Vertex 2: neighbours 0 1 4, degree 3
Vertex 3: neighbours 1 4, degree 2
Vertex 4: neighbours 2 3, degree 2
Sum of degrees: 12 (twice the 6 edges)

Directed and weighted graphs in a matrix

A weighted graph stores the weight where an unweighted one stores 1, and a directed graph fills only the cell of the edge's direction, so its rows and columns answer different questions.

1. Five one-way roads with their lengths. A directed edge fills only its own cell, matrix[from][to], so the matrix is no longer symmetric: matrix[2][1] = 2, but matrix[1][2] is empty — there is no road from 1 to 2.
2. Row 2 lists the roads leaving 2: to 1 and 3. Counting its filled cells gives the out-degree, 2.
3. Column 1 lists the roads arriving at 1: from 0 and 2. Its filled cells give the in-degree, 2.
4. Column 0 is empty, so no road leads to 0, and row 3 is empty, so none leaves 3. In a dependency graph those are the job that can start at once and the job nothing waits for.

The program prints the matrix, reads out-degrees from rows and in-degrees from columns, and checks two edges with one lookup each. Zero means "no edge" only because every weight is positive; when 0 is a possible weight, mark missing edges with a value no edge can have, such as a large number standing for infinity. In list form a weighted graph stores pairs: adj[u] holds (v, weight), which is what Dijkstra's algorithm reads.

#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

const int NO_EDGE = 0;  // safe because every weight here is positive

int main() {
    int n = 4;
    // {from, to, weight}: one-way roads and their lengths
    vector<vector<int>> edges = {{0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5}, {2, 3, 8}};

    vector<vector<int>> matrix(n, vector<int>(n, NO_EDGE));
    for (const vector<int>& e : edges) matrix[e[0]][e[1]] = e[2];  // directed: only the u -> v cell

    cout << "  ";
    for (int v = 0; v < n; v++) cout << setw(3) << v;
    cout << "\n";
    for (int u = 0; u < n; u++) {
        cout << u << " ";
        for (int v = 0; v < n; v++) {
            if (matrix[u][v] == NO_EDGE) cout << setw(3) << ".";
            else cout << setw(3) << matrix[u][v];
        }
        cout << "\n";
    }

    for (int u = 0; u < n; u++) {
        int outDegree = 0, inDegree = 0;
        for (int v = 0; v < n; v++) {
            if (matrix[u][v] != NO_EDGE) outDegree++;  // row u: edges leaving u
            if (matrix[v][u] != NO_EDGE) inDegree++;   // column u: edges arriving at u
        }
        cout << "Vertex " << u << ": out-degree " << outDegree << ", in-degree " << inDegree << "\n";
    }

    int checks[2][2] = {{2, 1}, {1, 2}};
    for (const auto& q : checks) {
        int w = matrix[q[0]][q[1]];  // one cell: an O(1) check
        cout << "Edge " << q[0] << " -> " << q[1] << ": ";
        if (w == NO_EDGE) cout << "no\n";
        else cout << "yes, weight " << w << "\n";
    }
    return 0;
}

public class Main {
    static final int NO_EDGE = 0; // safe because every weight here is positive

    public static void main(String[] args) {
        int n = 4;
        // {from, to, weight}: one-way roads and their lengths
        int[][] edges = {{0, 1, 4}, {0, 2, 1}, {2, 1, 2}, {1, 3, 5}, {2, 3, 8}};

        int[][] matrix = new int[n][n]; // Java fills it with 0, which is NO_EDGE
        for (int[] e : edges) matrix[e[0]][e[1]] = e[2]; // directed: only the u -> v cell

        StringBuilder header = new StringBuilder("  ");
        for (int v = 0; v < n; v++) header.append(String.format("%3d", v));
        System.out.println(header);
        for (int u = 0; u < n; u++) {
            StringBuilder row = new StringBuilder(u + " ");
            for (int v = 0; v < n; v++) {
                row.append(String.format("%3s", matrix[u][v] == NO_EDGE ? "." : String.valueOf(matrix[u][v])));
            }
            System.out.println(row);
        }

        for (int u = 0; u < n; u++) {
            int outDegree = 0, inDegree = 0;
            for (int v = 0; v < n; v++) {
                if (matrix[u][v] != NO_EDGE) outDegree++; // row u: edges leaving u
                if (matrix[v][u] != NO_EDGE) inDegree++;  // column u: edges arriving at u
            }
            System.out.println("Vertex " + u + ": out-degree " + outDegree + ", in-degree " + inDegree);
        }

        int[][] checks = {{2, 1}, {1, 2}};
        for (int[] q : checks) {
            int w = matrix[q[0]][q[1]]; // one cell: an O(1) check
            System.out.println("Edge " + q[0] + " -> " + q[1] + ": " + (w == NO_EDGE ? "no" : "yes, weight " + w));
        }
    }
}

NO_EDGE = 0  # safe because every weight here is positive

n = 4
# (from, to, weight): one-way roads and their lengths
edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 5), (2, 3, 8)]

matrix = [[NO_EDGE] * n for _ in range(n)]
for u, v, w in edges:
    matrix[u][v] = w  # directed: only the u -> v cell

print("  " + "".join(f"{v:>3}" for v in range(n)))
for u in range(n):
    cells = ("." if matrix[u][v] == NO_EDGE else str(matrix[u][v]) for v in range(n))
    print(f"{u} " + "".join(f"{c:>3}" for c in cells))

for u in range(n):
    out_degree = sum(1 for v in range(n) if matrix[u][v] != NO_EDGE)  # row u: edges leaving u
    in_degree = sum(1 for v in range(n) if matrix[v][u] != NO_EDGE)   # column u: edges arriving at u
    print(f"Vertex {u}: out-degree {out_degree}, in-degree {in_degree}")

for u, v in [(2, 1), (1, 2)]:
    w = matrix[u][v]  # one cell: an O(1) check
    print(f"Edge {u} -> {v}: " + ("no" if w == NO_EDGE else f"yes, weight {w}"))

const NO_EDGE = 0; // safe because every weight here is positive

const n = 4;
// [from, to, weight]: one-way roads and their lengths
const edges = [[0, 1, 4], [0, 2, 1], [2, 1, 2], [1, 3, 5], [2, 3, 8]];

const matrix = Array.from({ length: n }, () => new Array(n).fill(NO_EDGE));
for (const [u, v, w] of edges) matrix[u][v] = w; // directed: only the u -> v cell

let header = "  ";
for (let v = 0; v < n; v++) header += String(v).padStart(3);
console.log(header);
for (let u = 0; u < n; u++) {
  let row = `${u} `;
  for (let v = 0; v < n; v++) row += (matrix[u][v] === NO_EDGE ? "." : String(matrix[u][v])).padStart(3);
  console.log(row);
}

for (let u = 0; u < n; u++) {
  let outDegree = 0;
  let inDegree = 0;
  for (let v = 0; v < n; v++) {
    if (matrix[u][v] !== NO_EDGE) outDegree++; // row u: edges leaving u
    if (matrix[v][u] !== NO_EDGE) inDegree++; // column u: edges arriving at u
  }
  console.log(`Vertex ${u}: out-degree ${outDegree}, in-degree ${inDegree}`);
}

for (const [u, v] of [[2, 1], [1, 2]]) {
  const w = matrix[u][v]; // one cell: an O(1) check
  console.log(`Edge ${u} -> ${v}: ${w === NO_EDGE ? "no" : `yes, weight ${w}`}`);
}

    0  1  2  3
0   .  4  1  .
1   .  .  .  5
2   .  2  .  8
3   .  .  .  .
Vertex 0: out-degree 2, in-degree 0
Vertex 1: out-degree 1, in-degree 2
Vertex 2: out-degree 2, in-degree 1
Vertex 3: out-degree 0, in-degree 2
Edge 2 -> 1: yes, weight 2
Edge 1 -> 2: no

Grids and other hidden graphs

Many graph problems never say "graph". The commonest disguise is a grid: each open cell is a vertex, and you work out its neighbours on the fly with four direction offsets.

Check the bounds before you read the cell: grid[-1][c] is undefined behaviour in C++, an exception in Java and JavaScript, and a silent read of the last row in Python. A traversal of an R × C grid costs O(R × C); the matrix lesson covers grid indexing.

The second disguise is a state graph: each configuration is a vertex and each legal move an edge. In Open the Lock the vertices are the 10,000 four-digit codes, each leading to 8 others.

How to recognise a graph problem

• The input is a list of pairs [a, b], often with an n for the number of items.
• The words connection, network, friend, road, flight, neighbour or reachable.
• Dependencies: "must be done before", "prerequisite". That is a directed graph, very likely a DAG.
• A grid of cells you move through, or "the fewest moves" from one configuration to another.

Then the question picks the tool:

Common mistakes

• Storing an undirected edge once. Append to both lists, or a search can cross the edge one way only.
• Sharing one list between all the vertices. Create a fresh list per vertex.
• Off-by-one labels. When vertices are numbered 1 to n, size the arrays n + 1.
• A matrix for a large sparse graph. With V = 10⁵ it cannot fit in memory.
• Assuming the graph is connected. Vertices with no edges never appear in the edge list; loop over every vertex from 0 to n − 1.

Practice in this order

1. Find Center of Star Graph: degree alone; the centre is on every edge.
2. Find the Town Judge: in-degree and out-degree.
3. Find Champion II: the vertex with in-degree 0, and what two of them mean.
4. Find if Path Exists in Graph: build an adjacency list, then a first traversal.
5. Minimum Number of Vertices to Reach All Nodes: why every vertex with in-degree 0 must be chosen.
6. Maximal Network Rank: degrees plus a constant-time edge check.
7. Keys and Rooms: an adjacency list hiding in the input.
8. Number of Provinces: components of a graph given as a matrix.

The graph problem list has every graph problem in the catalogue, easiest first. Next comes the first way of searching one: breadth-first search.