Representations

The **adjacency matrix** is an n × n table with matrix[a][b] set when there is an edge from a to b (a weight for weighted graphs, a count for multigraphs). Asking whether an edge exists is one array read, O(1). The price is n² cells whatever the number of edges, and listing the neighbours of one vertex means scanning a whole row, O(n).

Watch the matrix in the animation as edges arrive. An undirected edge fills two mirror cells, a directed edge one. A self-loop adds 2 on the diagonal in this course, so every row sum equals the degree; other books put 1. The preset "Duplicate edge and self-loop" shows a cell counting 2 for a repeated edge.

1class AdjMatrix {
2    private final int[][] m;
3    private final boolean directed;
4    AdjMatrix(int n, boolean directed) { m = new int[n][n]; this.directed = directed; }
5    void addEdge(int a, int b) {
6        m[a][b]++;
7        if (!directed) m[b][a]++;                // a self-loop counts twice on the diagonal
8    }
9    boolean hasEdge(int a, int b) { return m[a][b] > 0; }      // O(1)
10    List<Integer> neighbours(int v) {            // O(n): scan the whole row
11        List<Integer> out = new ArrayList<>();
12        for (int u = 0; u < m.length; u++) if (m[v][u] > 0) out.add(u);
13        return out;
14    }
15}

1int[][] matrix = new int[n][n];                  // adjacency matrix: n * n cells
2List<List<int[]>> list = new ArrayList<>();      // adjacency list: {neighbour, weight} per vertex
3for (int i = 0; i < n; i++) list.add(new ArrayList<>());
4int[][] edgeList = new int[m][];                 // edge list: {a, b, weight}
5void addEdge(int k, int a, int b, int w, boolean directed) {
6    edgeList[k] = new int[]{a, b, w};
7    matrix[a][b]++;                              // directed: this one cell is the whole edge
8    list.get(a).add(new int[]{b, w});
9    if (!directed) {
10        matrix[b][a]++;                          // undirected: also the mirror cell (a self-loop counts twice on the diagonal)
11        list.get(b).add(new int[]{a, w});
12    }
13}

The **adjacency list** keeps, for every vertex, the list of its neighbours. It uses n + m space (n + 2m entries for an undirected graph), listing the neighbours of a vertex takes time proportional to its degree, and a whole traversal takes O(V + E). Testing whether one particular edge exists means scanning the list, O(degree). It is the default representation for most graph algorithms.

In the animation each vertex has a row list[v] that grows as edges are added; an undirected edge appears in both endpoints' lists, a directed edge only in the tail's. For weighted graphs each entry carries the weight (neighbour:weight).

1class AdjList {
2    private final List<List<int[]>> g = new ArrayList<>();    // {neighbour, weight}
3    private final boolean directed;
4    AdjList(int n, boolean directed) {
5        this.directed = directed;
6        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
7    }
8    void addEdge(int a, int b, int w) {
9        g.get(a).add(new int[]{b, w});
10        if (!directed) g.get(b).add(new int[]{a, w});
11    }
12    List<int[]> neighbours(int v) { return g.get(v); }   // O(degree)
13    int degree(int v) { return g.get(v).size(); }
14    boolean hasEdge(int a, int b) {              // O(degree of a)
15        for (int[] e : g.get(a)) if (e[0] == b) return true;
16        return false;
17    }
18}

1int[][] matrix = new int[n][n];                  // adjacency matrix: n * n cells
2List<List<int[]>> list = new ArrayList<>();      // adjacency list: {neighbour, weight} per vertex
3for (int i = 0; i < n; i++) list.add(new ArrayList<>());
4int[][] edgeList = new int[m][];                 // edge list: {a, b, weight}
5void addEdge(int k, int a, int b, int w, boolean directed) {
6    edgeList[k] = new int[]{a, b, w};
7    matrix[a][b]++;                              // directed: this one cell is the whole edge
8    list.get(a).add(new int[]{b, w});
9    if (!directed) {
10        matrix[b][a]++;                          // undirected: also the mirror cell (a self-loop counts twice on the diagonal)
11        list.get(b).add(new int[]{a, w});
12    }
13}

The **edge list** is just the list of edges, each as {a, b, weight}. It is the most compact form (m entries) and the natural input format. It is exactly what algorithms that process edges in an order want: Kruskal's algorithm sorts it by weight, Bellman-Ford loops over it. It is the worst for neighbour queries, which need a scan of the whole list, O(m).

Keep the original edge list even when you build an adjacency list for searching: it costs little and many algorithms (and reports, and tests) need the edges in input order. The animation shows it as the last row, one entry per edge in the order they were added.

1class EdgeList {
2    final List<int[]> edges = new ArrayList<>();             // {a, b, weight}
3    void add(int a, int b, int w) { edges.add(new int[]{a, b, w}); }
4    int[] degrees(int n) {                       // O(m): one pass over the edges
5        int[] deg = new int[n];
6        for (int[] e : edges) { deg[e[0]]++; deg[e[1]]++; }
7        return deg;
8    }
9    List<int[]> sortedByWeight() {               // what Kruskal's algorithm starts with
10        List<int[]> copy = new ArrayList<>(edges);
11        copy.sort(Comparator.comparingInt(e -> e[2]));
12        return copy;
13    }
14}

1int[][] matrix = new int[n][n];                  // adjacency matrix: n * n cells
2List<List<int[]>> list = new ArrayList<>();      // adjacency list: {neighbour, weight} per vertex
3for (int i = 0; i < n; i++) list.add(new ArrayList<>());
4int[][] edgeList = new int[m][];                 // edge list: {a, b, weight}
5void addEdge(int k, int a, int b, int w, boolean directed) {
6    edgeList[k] = new int[]{a, b, w};
7    matrix[a][b]++;                              // directed: this one cell is the whole edge
8    list.get(a).add(new int[]{b, w});
9    if (!directed) {
10        matrix[b][a]++;                          // undirected: also the mirror cell (a self-loop counts twice on the diagonal)
11        list.get(b).add(new int[]{a, w});
12    }
13}

The **incidence matrix** has one row per vertex and one column per edge. For an undirected edge, the two rows of its endpoints get 1 in that column; for a directed edge the tail gets -1 and the head +1. Each column of an undirected graph therefore sums to 2 and each column of a directed graph to 0 (for non-loop edges). It is n × m, usually larger than the adjacency matrix for sparse graphs, and is mostly of theoretical use: linear algebra on graphs, flow conservation, cycle spaces.

In flow problems the directed incidence matrix expresses 'flow in equals flow out' at every vertex as one matrix equation. In everyday programming you rarely build it, but knowing it explains the sign conventions you meet in network-flow texts.

1static int[][] incidence(int n, int[][] edges, boolean directed) {         // row = vertex, column = edge
2    int[][] inc = new int[n][edges.length];
3    for (int k = 0; k < edges.length; k++) {
4        int a = edges[k][0], b = edges[k][1];
5        if (directed) { inc[a][k] -= 1; inc[b][k] += 1; }    // tail -1, head +1
6        else { inc[a][k] += 1; inc[b][k] += 1; }             // both ends +1 (a self-loop gets 2)
7    }
8    return inc;
9}

**Compressed sparse row** (CSR) stores all neighbour lists back to back in one int[] target, plus an int[] offset where offset[v] is the start of vertex v's block and offset[v + 1] its end. It has no per-vertex objects and no pointers: scanning neighbours is a contiguous read, which is very fast, and the memory is exactly n + 1 + m ints for a directed graph. The price is that it is static: adding an edge means rebuilding.

Building takes two passes: count each vertex's degree into offset[v + 1], turn the counts into start positions with a prefix sum, then place each neighbour in its block. The animation shows the three steps. In the preset "Undirected: every edge twice" the neighbours of vertex 3 are [1, 2, 4], read from target[6..8].

1static int[][] buildCsr(int n, int[][] edges, boolean directed) {         // returns {offset, target}
2    int[] offset = new int[n + 1];
3    for (int[] e : edges) {                      // pass 1: count the out-degree of every vertex
4        offset[e[0] + 1]++;
5        if (!directed) offset[e[1] + 1]++;
6    }
7    for (int v = 0; v < n; v++) offset[v + 1] += offset[v];            // prefix sums: where each block starts
8    int[] target = new int[offset[n]], next = offset.clone();
9    for (int[] e : edges) {                      // pass 2: write every neighbour into its block
10        target[next[e[0]]++] = e[1];
11        if (!directed) target[next[e[1]]++] = e[0];
12    }
13    return new int[][]{offset, target};
14}

1static int[][] buildCsr(int n, int[][] edges, boolean directed) {   // returns {offset, target}
2    int[] offset = new int[n + 1];
3    for (int[] e : edges) {                      // pass 1: count the out-degree of every vertex
4        offset[e[0] + 1]++;
5        if (!directed) offset[e[1] + 1]++;
6    }
7    for (int v = 0; v < n; v++) offset[v + 1] += offset[v];          // prefix sums: where each vertex's block starts
8    int[] target = new int[offset[n]], next = offset.clone();
9    for (int[] e : edges) {                      // pass 2: write every neighbour into its block
10        target[next[e[0]]++] = e[1];
11        if (!directed) target[next[e[1]]++] = e[0];
12    }
13    return new int[][]{offset, target};
14}
15// the neighbours of v are target[offset[v]] .. target[offset[v + 1] - 1]