15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
An adjacency matrix is a V by V table where cell M[u][v] is 1 when an edge connects u and v, and 0 otherwise. For an undirected graph you set both M[u][v] and M[v][u]. One edge test is a single cell read, O(1), but the table stores V squared cells.
| Storage | Matrix O(V^2), list O(V + E) |
|---|---|
| Test whether u-v exists | Matrix O(1), list O(deg(u)) |
| List the neighbors of u | Matrix O(V), scan one row; list O(deg(u)) |
| Build time | Matrix O(V^2), list O(V + E) |
| Undirected rule | Write both directions: M[u][v] = M[v][u] = 1 |
Assume you know these graph terms:
A.A-B can be traveled in either direction.We will store the same undirected graph in two ways:
V × V table, where V is the number of vertices.For an unweighted graph, matrix entry M[u,v] means:
1: an edge connects u and v.0: no edge connects u and v.A matrix needs numeric positions. For this lesson, keep the vertex order fixed:
| Vertex | Matrix index |
|---|---|
| A | 0 |
| B | 1 |
| C | 2 |
| D | 3 |
Row A and column A mean index 0. Row D and column D mean index 3.
Use these ordered vertices and undirected edges:
1Vertices: [A, B, C, D]
2Edges: A-B, A-C, B-D, C-DThe graph has four vertices. Vertex order is always:
1[A, B, C, D]An adjacency list starts with one empty list per vertex:
1A: []
2B: []
3C: []
4D: []An adjacency matrix starts as a 4 × 4 table of zeros:
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 0 | 0 | 0 |
| B | 0 | 0 | 0 | 0 |
| C | 0 | 0 | 0 | 0 |
| D | 0 | 0 | 0 | 0 |
The graph is undirected. Storing edge A-B requires two representation updates:
B goes into A’s neighbor list.A goes into B’s neighbor list.For the matrix, both mirrored cells become 1:
1M[A,B] = 1
2M[B,A] = 1Start at State 0. Process the edge list from left to right.
Adding A-B, A-C, B-D, C-D one at a time: each edge appends to two lists and sets two mirrored matrix cells. The final matrix rows are 0110, 1001, 1001, 0110.
Even a vertex with no edges needs a list entry and a matrix row and column.
1Lists
2A: []
3B: []
4C: []
5D: []1Matrix
2 A B C D
3A : 0 0 0 0
4B : 0 0 0 0
5C : 0 0 0 0
6D : 0 0 0 0Append B to A’s list.
1A: [B]Append A to B’s list.
1B: [A]The other lists have not changed.
1A: [B]
2B: [A]
3C: []
4D: []Now update two matrix cells:
1M[A,B] = 1
2M[B,A] = 11 A B C D
2A : 0 1 0 0
3B : 1 0 0 0
4C : 0 0 0 0
5D : 0 0 0 0Append C to A’s list.
1A: [B, C]Append A to C’s list.
1C: [A]Lists now are:
1A: [B, C]
2B: [A]
3C: [A]
4D: []Set the symmetric matrix cells:
1M[A,C] = 1
2M[C,A] = 11 A B C D
2A : 0 1 1 0
3B : 1 0 0 0
4C : 1 0 0 0
5D : 0 0 0 0Append D to B’s list and B to D’s list.
1A: [B, C]
2B: [A, D]
3C: [A]
4D: [B]Set both matrix directions:
1M[B,D] = 1
2M[D,B] = 11 A B C D
2A : 0 1 1 0
3B : 1 0 0 1
4C : 1 0 0 0
5D : 0 1 0 0Append D to C’s list and C to D’s list.
1A: [B, C]
2B: [A, D]
3C: [A, D]
4D: [B, C]Set both matrix directions:
1M[C,D] = 1
2M[D,C] = 1Final matrix:
1 A B C D
2A : 0 1 1 0
3B : 1 0 0 1
4C : 1 0 0 1
5D : 0 1 1 0Written as rows:
1A: 0110
2B: 1001
3C: 1001
4D: 0110To test adjacency with the matrix, read one cell:
1M[A,D] = 0So A-D is not an edge.
To test adjacency with the list, scan A’s neighbors:
1A: [B, C]D is absent, so A-D is not an edge.
After each processed edge, the two representations agree about every edge processed so far.
More precisely:
After processing any prefix of the undirected edge list, each processed edge
u-vappears once inu’s neighbor list and once inv’s neighbor list, and the matrix has equal entriesM[u,v] = M[v,u] = 1.
The statement is the loop invariant.
Look back at the states:
A-B, both directions are present.A-C, the earlier edge A-B is still stored correctly, and A-C is now stored in both directions.B-D, A-B and A-C remain stored correctly, and B-D is stored in both directions.C-D, all four processed edges are stored in both directions.The fixed order [A,B,C,D] also stays true. A always maps to index 0, B to 1, C to 2, and D to 3. If that mapping changes halfway through construction, a matrix cell can describe the wrong pair of vertices.
Use a simple binary matrix:
0 or 1.A-A, if allowed by the surrounding graph model, is represented by M[A,A] = 1. Its list policy must also be stated. One possible policy is to append A twice, representing the two incidences of the loop.We need two construction procedures.
V empty neighbor lists.(u,v).v to u’s list.u to v’s list.For the worked example, the labels map to indices like this:
1A-B becomes (0,1)
2A-C becomes (0,2)
3B-D becomes (1,3)
4C-D becomes (2,3)V × V table filled with zero.(u,v).M[u,v] to 1.M[v,u] to 1.The two procedures store different shapes of data:
1Adjacency list:
2one variable-length neighbor collection per vertex
3
4Adjacency matrix:
5one fixed V by V tableTo list all neighbors of u:
u.u and collect columns containing 1.To test whether a possible edge u-v exists:
M[u,v].u’s neighbor collection for v.The executable practice uses vertex indices from 0 through vertexCount - 1.
1REQUIRE VALIDVERTEX(vertexCount, vertex)
2
3Input:
4 vertexCount: nonnegative integer
5 vertex: integer
6
7Behavior:
8 Stops with a validation failure if vertex < 0 or vertex >= vertexCount.
9 Otherwise returns normally.
10
11Mutation:
12 Does not modify any input.1FUNCTION buildUndirectedAdjacencyList(vertexCount, edges) -> adjacencyList
2 # Input:
3 # vertexCount: number of vertices, indexed 0 through vertexCount - 1
4 # edges: sequence of pairs (u, v)
5 #
6 # Precondition:
7 # edges contains no duplicate undirected edges.
8 #
9 # Mutation:
10 # Does not modify edges. Creates and returns a new adjacency list.
11 #
12 # Return:
13 # adjacencyList[u] contains every neighbor of u.
14
151 adjacencyList <- new collection containing vertexCount empty lists
16
172 FOR EACH (u, v) IN edges
183 REQUIRE VALIDVERTEX(vertexCount, u)
194 REQUIRE VALIDVERTEX(vertexCount, v)
205 APPEND v TO adjacencyList[u]
216 APPEND u TO adjacencyList[v]
227 END FOR
23
248 RETURN adjacencyList
25END FUNCTION1FUNCTION buildUndirectedAdjacencyMatrix(vertexCount, edges) -> matrix
2 # Input:
3 # vertexCount: number of vertices, indexed 0 through vertexCount - 1
4 # edges: sequence of pairs (u, v)
5 #
6 # Precondition:
7 # edges contains no duplicate undirected edges.
8 #
9 # Mutation:
10 # Does not modify edges. Creates and returns a new matrix.
11 #
12 # Return:
13 # matrix[u][v] is 1 exactly when the input includes edge u-v.
14
151 matrix <- new vertexCount by vertexCount table filled with 0
16
172 FOR EACH (u, v) IN edges
183 REQUIRE VALIDVERTEX(vertexCount, u)
194 REQUIRE VALIDVERTEX(vertexCount, v)
205 matrix[u][v] <- 1
216 matrix[v][u] <- 1
227 END FOR
23
248 RETURN matrix
25END FUNCTIONFor a directed edge u → v, the insertion rule is different:
1adjacencyList[u].append(v)
2matrix[u][v] <- 1Do not add the reverse direction unless the graph is undirected.
Use the worked example with this index mapping:
1A = 0, B = 1, C = 2, D = 3
2
3edges = [(0,1), (0,2), (1,3), (2,3)]
4vertexCount = 4Line 1 creates four empty lists.
10: [] meaning A: []
21: [] meaning B: []
32: [] meaning C: []
43: [] meaning D: []First loop iteration, line 2: (u,v) = (0,1), which is A-B.
0 is valid.1 is valid.1 to list 0.0 to list 1.1A: [B]
2B: [A]
3C: []
4D: []Second loop iteration, line 2: (u,v) = (0,2), which is A-C.
0 is valid.2 is valid.2 to list 0.0 to list 2.1A: [B, C]
2B: [A]
3C: [A]
4D: []Third loop iteration, line 2: (u,v) = (1,3), which is B-D.
1 is valid.3 is valid.3 to list 1.1 to list 3.1A: [B, C]
2B: [A, D]
3C: [A]
4D: [B]Fourth loop iteration, line 2: (u,v) = (2,3), which is C-D.
2 is valid.3 is valid.3 to list 2.2 to list 3.1A: [B, C]
2B: [A, D]
3C: [A, D]
4D: [B, C]The loop ends. Line 8 returns these lists.
Line 1 creates a 4 × 4 matrix of zeroes.
1 A B C D
2A : 0 0 0 0
3B : 0 0 0 0
4C : 0 0 0 0
5D : 0 0 0 0First loop iteration: (u,v) = (0,1).
matrix[0][1] to 1, so M[A,B] = 1.matrix[1][0] to 1, so M[B,A] = 1.1 A B C D
2A : 0 1 0 0
3B : 1 0 0 0
4C : 0 0 0 0
5D : 0 0 0 0Second loop iteration: (u,v) = (0,2).
M[A,C] = 1.M[C,A] = 1.1 A B C D
2A : 0 1 1 0
3B : 1 0 0 0
4C : 1 0 0 0
5D : 0 0 0 0Third loop iteration: (u,v) = (1,3).
M[B,D] = 1.M[D,B] = 1.1 A B C D
2A : 0 1 1 0
3B : 1 0 0 1
4C : 1 0 0 0
5D : 0 1 0 0Fourth loop iteration: (u,v) = (2,3).
M[C,D] = 1.M[D,C] = 1.1 A B C D
2A : 0 1 1 0
3B : 1 0 0 1
4C : 1 0 0 1
5D : 0 1 1 0The loop ends. Line 8 returns this matrix.
Consider either construction algorithm processing an undirected edge list.
Before the loop begins:
0.No edges have been processed yet. Therefore, there are no processed edges that need to appear in lists or matrix cells. The invariant holds initially.
The initialization also handles isolated vertices. A vertex remains present even if no edge ever mentions it.
Assume the invariant holds before processing the next edge (u,v).
The list procedure:
v to u’s neighbor list.u to v’s neighbor list.So the new edge appears in both required directions. Earlier processed edges are not removed or changed.
The matrix procedure:
1 to M[u,v].1 to M[v,u].So the new edge has equal symmetric entries. Earlier 1 entries remain unchanged.
After processing this edge, every processed edge is represented in both directions. The invariant is preserved.
The loop processes every edge in the input exactly once.
When the loop ends, the processed prefix is the entire edge list. By the invariant:
1 in both corresponding matrix cells;Both procedures construct the required undirected graph representation.
Let:
V be the number of vertices.E be the number of undirected edges.First, create V empty lists.
1Work: V bucket creationsThat costs O(V).
Then process E edges. Each undirected edge performs two constant-time appends:
1append v to adjacencyList[u]
2append u to adjacencyList[v]That is 2E appends, which is O(E).
Combined construction work:
1O(V) + O(E) = O(V + E)Storage includes:
V list references;So adjacency-list storage is:
1O(V + E)To test whether u-v might exist using the list, scan u’s neighbors. If u has deg(u) neighbors, that scan costs:
1O(deg(u))To list every neighbor of u, read its stored list:
1O(deg(u))Creating the matrix initializes every cell.
A V × V matrix has:
1V × V = V² cellsEach cell is written during initialization, so construction costs:
1O(V²)The later edge writes do not change that bound because the full matrix initialization already touches V² cells.
The matrix stores all V² cells, so storage is:
1O(V²)To test whether u-v exists, read one cell:
1M[u,v]That costs:
1O(1)To list all neighbors of u, scan all V entries in row u:
1O(V)Choose an adjacency list when stored neighbors should be read directly. Choose an adjacency matrix when direct M[u,v] lookups justify O(V²) storage.
| Operation | Adjacency list | Adjacency matrix |
|---|---|---|
| Storage | O(V+E) | O(V²) |
Test whether u-v exists | O(deg(u)) | O(1) |
List neighbors of u | O(deg(u)) | O(V) |
Incorrect operation for undirected edge A-B:
1APPEND B TO adjacencyList[A]Smallest exposing input:
1Vertices: [A, B]
2Edges: A-BWrong state:
1A: [B]
2B: []A query for B’s neighbors incorrectly says that B has none.
Correction:
1APPEND B TO adjacencyList[A]
2APPEND A TO adjacencyList[B]Incorrect operation:
1M[A,B] <- 1Smallest exposing input:
1Undirected edge: A-BWrong matrix:
1 A B
2A : 0 1
3B : 0 0The matrix is not symmetric. A query for B-A reads 0 and incorrectly reports no edge.
Correction:
1M[A,B] <- 1
2M[B,A] <- 1Incorrect assumption:
1matrix has E rows and E columnsExposing input:
1V = 4
2E = 1
3Edge: A-DA 1 × 1 matrix has no row or column for D. Matrix dimensions describe possible vertex pairs, not the number of input edges.
Correction:
1matrix has V rows and V columnsFor four vertices, allocate a 4 × 4 matrix even when there is only one edge.
Suppose the stated order is:
1[A, B, C]Then the correct indices are:
1A = 0, B = 1, C = 2Exposing input:
1Edge: A-CIncorrect mapping during insertion:
1A = 0, C = 1The mapping marks the A-B relationship incorrectly, or can lead to a B-C mark if rows and columns use different inconsistent mappings.
Correction: create one mapping and use it for every row, column, and edge endpoint.
1A -> 0
2B -> 1
3C -> 2| Input | Required result |
|---|---|
Vertices [A,B,C], no edges | Lists A:[], B:[], C:[]; all-zero 3 × 3 matrix |
Vertex [A], no edges | One empty list; matrix [0] |
Directed edge A → B | A:[B], B:[]; M[A,B]=1, M[B,A]=0 |
Undirected self-loop A-A | Document M[A,A]=1 and the chosen list policy |
Vertices [A,B], edge references Z | Validation failure, not an out-of-range matrix write |
A zero matrix entry and a missing list entry both mean that the representation currently contains no such edge. Do not infer an edge where neither representation stores one.
Implement:
1buildUndirectedAdjacencyList(vertexCount, edges)
2buildUndirectedAdjacencyMatrix(vertexCount, edges)Executable tests verify this contract:
vertexCount × vertexCount.1LABELS = "ABCD"
2EDGES = [(0, 1), (0, 2), (1, 3), (2, 3)] # A-B, A-C, B-D, C-D
3
4def require_valid(n, *vertices):
5 for x in vertices:
6 if not 0 <= x < n:
7 raise ValueError(f"vertex {x} out of range")
8
9def build_list(n, edges):
10 adj = [[] for _ in range(n)]
11 for u, v in edges:
12 require_valid(n, u, v)
13 adj[u].append(v)
14 adj[v].append(u)
15 return adj
16
17def build_matrix(n, edges):
18 m = [[0] * n for _ in range(n)]
19 for u, v in edges:
20 require_valid(n, u, v)
21 m[u][v] = 1
22 m[v][u] = 1
23 return m
24
25adj = build_list(4, EDGES)
26matrix = build_matrix(4, EDGES)
27for i, row in enumerate(adj):
28 print(f"{LABELS[i]}: [{', '.join(LABELS[j] for j in row)}]")
29for i, row in enumerate(matrix):
30 print(f"{LABELS[i]}: {''.join(str(x) for x in row)}")
31print("M[A][D] =", matrix[0][3])1import java.util.*;
2
3public class Main {
4 static final String LABELS = "ABCD";
5
6 static void requireValid(int n, int... vertices) {
7 for (int x : vertices) {
8 if (x < 0 || x >= n) throw new IllegalArgumentException("vertex " + x + " out of range");
9 }
10 }
11
12 static List<List<Integer>> buildList(int n, int[][] edges) {
13 List<List<Integer>> adj = new ArrayList<>();
14 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
15 for (int[] e : edges) {
16 requireValid(n, e[0], e[1]);
17 adj.get(e[0]).add(e[1]);
18 adj.get(e[1]).add(e[0]);
19 }
20 return adj;
21 }
22
23 static int[][] buildMatrix(int n, int[][] edges) {
24 int[][] m = new int[n][n];
25 for (int[] e : edges) {
26 requireValid(n, e[0], e[1]);
27 m[e[0]][e[1]] = 1;
28 m[e[1]][e[0]] = 1;
29 }
30 return m;
31 }
32
33 public static void main(String[] args) {
34 int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}}; // A-B, A-C, B-D, C-D
35 List<List<Integer>> adj = buildList(4, edges);
36 int[][] matrix = buildMatrix(4, edges);
37 for (int i = 0; i < 4; i++) {
38 StringBuilder sb = new StringBuilder();
39 for (int j : adj.get(i)) sb.append(sb.length() > 0 ? ", " : "").append(LABELS.charAt(j));
40 System.out.println(LABELS.charAt(i) + ": [" + sb + "]");
41 }
42 for (int i = 0; i < 4; i++) {
43 StringBuilder sb = new StringBuilder();
44 for (int x : matrix[i]) sb.append(x);
45 System.out.println(LABELS.charAt(i) + ": " + sb);
46 }
47 System.out.println("M[A][D] = " + matrix[0][3]);
48 }
49}1#include <iostream>
2#include <stdexcept>
3#include <string>
4#include <utility>
5#include <vector>
6using namespace std;
7
8const string LABELS = "ABCD";
9
10void requireValid(int n, int v) {
11 if (v < 0 || v >= n) throw invalid_argument("vertex out of range");
12}
13
14vector<vector<int>> buildList(int n, const vector<pair<int, int>>& edges) {
15 vector<vector<int>> adj(n);
16 for (const auto& e : edges) {
17 requireValid(n, e.first);
18 requireValid(n, e.second);
19 adj[e.first].push_back(e.second);
20 adj[e.second].push_back(e.first);
21 }
22 return adj;
23}
24
25vector<vector<int>> buildMatrix(int n, const vector<pair<int, int>>& edges) {
26 vector<vector<int>> m(n, vector<int>(n, 0));
27 for (const auto& e : edges) {
28 requireValid(n, e.first);
29 requireValid(n, e.second);
30 m[e.first][e.second] = 1;
31 m[e.second][e.first] = 1;
32 }
33 return m;
34}
35
36int main() {
37 vector<pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 3}, {2, 3}}; // A-B, A-C, B-D, C-D
38 auto adj = buildList(4, edges);
39 auto matrix = buildMatrix(4, edges);
40 for (int i = 0; i < 4; i++) {
41 cout << LABELS[i] << ": [";
42 for (size_t k = 0; k < adj[i].size(); k++) cout << (k ? ", " : "") << LABELS[adj[i][k]];
43 cout << "]\n";
44 }
45 for (int i = 0; i < 4; i++) {
46 cout << LABELS[i] << ": ";
47 for (int x : matrix[i]) cout << x;
48 cout << "\n";
49 }
50 cout << "M[A][D] = " << matrix[0][3] << endl;
51}1const LABELS = 'ABCD';
2const EDGES = [[0, 1], [0, 2], [1, 3], [2, 3]]; // A-B, A-C, B-D, C-D
3
4function requireValid(n, ...vertices) {
5 for (const x of vertices) {
6 if (x < 0 || x >= n) throw new Error(`vertex ${x} out of range`);
7 }
8}
9
10function buildList(n, edges) {
11 const adj = Array.from({ length: n }, () => []);
12 for (const [u, v] of edges) {
13 requireValid(n, u, v);
14 adj[u].push(v);
15 adj[v].push(u);
16 }
17 return adj;
18}
19
20function buildMatrix(n, edges) {
21 const m = Array.from({ length: n }, () => new Array(n).fill(0));
22 for (const [u, v] of edges) {
23 requireValid(n, u, v);
24 m[u][v] = 1;
25 m[v][u] = 1;
26 }
27 return m;
28}
29
30const adj = buildList(4, EDGES);
31const matrix = buildMatrix(4, EDGES);
32adj.forEach((row, i) => console.log(`${LABELS[i]}: [${row.map((j) => LABELS[j]).join(', ')}]`));
33matrix.forEach((row, i) => console.log(`${LABELS[i]}: ${row.join('')}`));
34console.log(`M[A][D] = ${matrix[0][3]}`);Take vertices A, B, C, D at indices 0 to 3 and edges A-B, A-C, B-D, C-D. The rows are A: 0110, B: 1001, C: 1001, D: 0110. Row A has 1s in columns B and C, so A is adjacent to B and C.
Make a V by V table of zeros. For each edge (u, v), check both indices are valid, then set M[u][v] and M[v][u] to 1. For a directed edge u to v, set only M[u][v].
It answers whether u and v share an edge with one cell read. It also gives every vertex a fixed row and column, including isolated vertices, so the layout never changes while you build it.
Use a list when you mostly read each vertex's neighbors, since storage is O(V + E). Use a matrix when direct M[u][v] lookups justify O(V^2) storage.
Rows and columns stand for vertices. A graph with 4 vertices and one edge still needs a 4 by 4 matrix, because every possible vertex pair needs a cell.