GraphsData structureaka connection matrix, V×V matrix

Adjacency Matrix

A V×V grid where cell [u][v] stores whether (or how heavily) u connects to v, giving O(1) edge lookup at O(V²) space.

▶ Visualize Pattern: Depth-First Search Practice (3)

Progress

Definition

An adjacency matrix represents a graph with V vertices as a V × V array M. For an unweighted graph M[u][v] = 1 if edge u → v exists and 0 otherwise; for a Weighted Graph it stores the weight, with ∞ (or null) for "no edge". An Undirected Graph has a symmetric matrix.

Its strength is O(1) edge existence and weight lookup, and natural algebraic operations: M²[u][v] counts length-2 walks, Floyd-Warshall runs directly on the matrix, and the transpose is the reversed graph. Its weakness is O(V²) memory regardless of E, and O(V) to enumerate neighbors, which makes Breadth-First Search (BFS) and Depth-First Search (DFS) O(V²).

Use it when the graph is dense (E close to V²), when V ≤ ~10⁴, or when the algorithm is matrix-shaped. For sparse graphs an Adjacency List is strictly better.

dense graphO(1) edge lookupO(V²) spaceFloyd-Warshallmatrix power

Intuition

A mental model before the formal terms.

A mileage chart in the back of a road atlas: cities down the side and across the top, and the number where a row meets a column is the distance. Looking up any pair is instant; listing everywhere reachable from one city means scanning an entire row, including all the blanks.

The chart has as many cells as there are city pairs. With 1,000 cities that is a million cells even if there are only 2,000 roads — 99.8% blank.

How it works

Allocate M as V rows of V cells initialised to 0 (unweighted) or ∞ (weighted). Set M[u][u] = 0 for weighted matrices if self-distance is used.
addEdge(u, v, w): M[u][v] = w; for undirected also M[v][u] = w.
hasEdge(u, v): M[u][v] != 0 (or != ∞).
neighbors(u): iterate v from 0 to V-1 and yield those with M[u][v] set — O(V) regardless of degree.
Floyd-Warshall: for k: for i: for j: M[i][j] = min(M[i][j], M[i][k] + M[k][j]) computes all-pairs shortest paths in place.
Bit-packing: for unweighted graphs each row can be a bitset, cutting memory by 64× and enabling fast transitive-closure via bitwise OR.

Why it works

The matrix is a direct encoding of the edge relation as a function V × V → {0, 1} (or weights), so lookup is array indexing.

Matrix multiplication counts walks: (M^k)[u][v] = Σ over intermediate vertices of products of edge indicators, which is exactly the number of length-k walks from u to v.

Floyd-Warshall is DP over the matrix: after iteration k, M[i][j] is the shortest path using only intermediates ≤ k.

Operations

Operation	Description	Cost
addEdge(u, v, w)	Set one cell (two for undirected).	O(1)
removeEdge(u, v)	Reset the cell.	O(1)
hasEdge / weight(u, v)	Read the cell.	O(1)
neighbors(u)	Scan row u.	O(V)
degree(u)	Count non-empty cells in row u (or maintain a counter).	O(V)
addVertex	Reallocate a (V+1)×(V+1) matrix.	O(V²)
transpose	Swap M[i][j] and M[j][i]; gives the reversed graph.	O(V²)
allPairs (Floyd-Warshall)	In-place DP.	O(V³)

Recognition

How to tell a problem wants this.

The input is already given as a matrix (isConnected[i][j], graph[i][j], a distance table).
V ≤ 500 or so, and you need all-pairs shortest paths or transitive closure.
Frequent "is there an edge between u and v" queries on a dense graph.
Problems phrased in terms of walks of length k or matrix exponentiation.

“connected groups” → Depth-First Search “weighted graph” → Shortest Path (Weighted)“number of ways” → Dynamic Programming

Interactive demo

Play, step, change the input. ← → and space work too.

Showing the closely related Floyd-Warshall visualization.

Weighted graph — One edge per line: "A B 4". At most 7 nodes (the table is n×n).

	A	B	C	D	E
A	0	3	∞	∞	8
B	∞	0	1	7	∞
C	2	∞	0	1	∞
D	∞	∞	∞	0	2
E	4	∞	∞	∞	0

1/39Initialize the 5×5 matrix from the edge weights: 0 on the diagonal, ∞ where no edge exists. dist[i][j] means "best path from i to j using no intermediate nodes yet".

Row k / column k (paths through k)Cell being updatedImproved in this k-phaseDiagonal (always 0)

PseudocodeLearn Floyd-Warshall →

1dist[i][j] = w(i,j) if edge, 0 if i == j, else ∞
2for k in nodes:          # allowed intermediate
3  for i in nodes:
4    for j in nodes:
5      if dist[i][k] + dist[k][j] < dist[i][j]:
6        dist[i][j] = dist[i][k] + dist[k][j]
7return dist

Complexity

best O(V³)

avg O(V³)

worst O(V³)

space O(V²)

Speed

Pseudocode

1M = [[INF]*V for _ in range(V)]; M[i][i] = 0
2add_edge(u, v, w): M[u][v] = w  (and M[v][u] = w if undirected)
3has_edge(u, v): return M[u][v] != INF
4neighbors(u): return [v for v in range(V) if M[u][v] != INF and v != u]
5floyd_warshall(): for k: for i: for j: M[i][j] = min(M[i][j], M[i][k] + M[k][j])

Implementation

1class AdjacencyMatrix:
2    """n x n boolean (or weight) grid: cell (u, v) says whether u -> v exists.
3    Dense storage: O(V^2) memory regardless of how many edges there are."""
4 
51 · State: a flat V*V bytearray indexed as u * n + v
6    def __init__(self, n: int, directed: bool = False) -> None:
7        self.n = n
8        self.directed = directed
9        self.cells = bytearray(n * n)
10 
112 · Edge insertion and lookup are both O(1) — the defining advantage
12    def add_edge(self, u: int, v: int) -> None:
13        self.cells[u * self.n + v] = 1
14        if not self.directed:
15            self.cells[v * self.n + u] = 1
16 
17    def has_edge(self, u: int, v: int) -> bool:
18        return self.cells[u * self.n + v] != 0
19 
203 · Enumerating neighbours costs O(V), even for a vertex of degree 1
21    def neighbours(self, u: int) -> list[int]:
22        base = u * self.n
23        return [v for v in range(self.n) if self.cells[base + v]]
24 
254 · A full traversal is O(V^2), which is why sparse graphs use lists
26    def edge_count(self) -> int:
27        count = sum(self.cells)
28        return count if self.directed else count // 2  # undirected cells are symmetric
29 
305 · Transpose reverses every edge by mirroring across the diagonal
31    def transposed(self) -> "AdjacencyMatrix":
32        t = AdjacencyMatrix(self.n, directed=True)
33        for u in range(self.n):
34            base = u * self.n
35            for v in range(self.n):
36                if self.cells[base + v]:
37                    t.cells[v * self.n + u] = 1
38        return t

Walkthrough

bytearray(n * n) is a mutable, contiguous, zero-filled byte buffer — the closest Python equivalent to a Uint8Array.
neighbours hoists base = u * self.n out of the comprehension so the multiplication happens once per call rather than once per column.
sum(self.cells) counts set cells in C, which is far faster than a Python-level double loop over V^2 cells.
count // 2 halves the undirected total; integer division makes the intent explicit and avoids a float result.
if self.cells[base + v] relies on 0 being falsy, which is idiomatic Python and avoids an explicit != 0.

Complexity (this implementation)

time O(1) add_edge and has_edge, O(V) neighbours, O(V^2) traversal · space O(V^2)

bytearray stores one byte per cell; a list[list[int]] would store pointers to boxed ints and use roughly 60x more memory.

Language notes

bytearray gives one byte per cell with no boxing; a nested list of int is the naive version and is enormous by comparison.
NumPy is the real answer for anything matrix-shaped: np.zeros((n, n), dtype=np.uint8) plus vectorised row operations, and m.T for the transpose.
sum(bytearray) iterates in C; the equivalent sum(1 for c in cells if c) is a Python-level loop and much slower.
scipy.sparse bridges the two worlds when the graph is sparse but matrix algebra is still wanted.

Common mistakes in this language

Assigning a value above 255 into a bytearray, which raises ValueError rather than truncating (unlike Uint8Array in JavaScript).
Building the matrix as [[0] * n] * n, which aliases one row n times — the same trap as the adjacency list.
Reaching for a matrix on a sparse graph, where scipy.sparse or a defaultdict(list) is orders of magnitude smaller.

Language differences that matter here

Byte-dense storage: C++ std::vector<std::uint8_t>, JS/TS Uint8Array, Python bytearray — and in every case the naive nested container is roughly an order of magnitude larger.
std::vector<bool> is a unique C++ trap: it bit-packs and returns a proxy from operator[], so it is deliberately avoided here in favour of uint8_t.
Out-of-range writes: Uint8Array truncates silently (256 becomes 0), Python bytearray raises ValueError, and C++ operator[] is undefined behaviour — three different reactions to the same mistake.
Index overflow in u * n + v is a real hazard only in C++ with 32-bit int; JavaScript doubles stay exact to 2^53 and Python integers are unbounded.

Complexity

Operation	Average	Worst	Note
Access	O(1)	O(1)	Edge (u, v) by index.
Search	O(1)	O(1)	Edge existence.
Insert	O(1)	O(1)	Edge; adding a vertex is O(V²).
Delete	O(1)	O(1)	Edge.
Update	O(1)	O(1)	Change a weight.
Neighbors	O(V)	O(V)
BFS / DFS	O(V²)	O(V²)
Floyd-Warshall	O(V³)	O(V³)
Space	O(V²)		Independent of E; bitset rows reduce the constant by 64×.

Advantages & disadvantages

Advantages

O(1) edge lookup, insertion, and deletion.
Simple, cache-friendly for dense graphs; no pointers or dynamic allocation.
Algebraic operations (powers, transpose, Floyd-Warshall) map directly onto the array.
Bitset rows make transitive closure and set operations very fast.

Disadvantages

O(V²) memory even for a graph with V edges — infeasible past V ≈ 10⁴–10⁵.
Enumerating neighbors is O(V), so BFS/DFS become O(V²) instead of O(V + E).
Adding a vertex requires reallocating the whole matrix.
Cannot represent parallel edges without extra structure (only one cell per pair).

Use cases

Floyd-Warshall all-pairs shortest paths.
Number of Provinces / friend circles given as isConnected[i][j].
Transitive closure and reachability matrices.
Counting walks and paths of a fixed length via matrix exponentiation.
Small dense graphs in DP-over-subsets problems (Bitmask DP, TSP).

Use it when

Dense graphs where E ≈ V².
Frequent O(1) edge-existence or weight queries.
All-pairs algorithms (Floyd-Warshall), transitive closure, walk counting.
Small V (≤ a few thousand) where simplicity matters more than memory.

Avoid it when

Sparse graphs with large V — memory is O(V²) and traversals are O(V²); use an Adjacency List.
Vertices are added dynamically — resizing the matrix is O(V²).
Multigraphs with parallel edges — a cell holds only one value.

Alternatives

Adjacency List Edge List

Common mistakes

Using 0 as "no edge" in a weighted matrix where zero-weight edges are legal.
Using Integer.MAX_VALUE as infinity and overflowing on d[i][k] + d[k][j] — use INF = MAX / 4 or check before adding.
Forgetting to set both M[u][v] and M[v][u] for undirected graphs.
Running BFS via row scans on a sparse graph with V = 10⁵ — 10¹⁰ operations.
Iterating k as the innermost loop in Floyd-Warshall — it must be the outermost.

Interview patterns

Number of Provinces: DFS/union-find over an isConnected matrix.
Find the Celebrity: knows(a, b) is a matrix oracle; two-pointer elimination.
Floyd-Warshall for "city with the smallest number of neighbors within threshold".
Count walks of length k with fast matrix exponentiation.
TSP / Hamiltonian path with bitmask DP over a distance matrix.

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
Stack versus queueBeginner
Recursion versus iterationIntermediate
When space complexity mattersIntermediate

Mock interviews

Course ScheduleIntermediate
Network Delay TimeAdvanced
Number of IslandsIntermediate

Interview problems

Shortest Path Visiting All Nodeshard Number of Connected Componentsmedium Network Delay Timemedium

Definition

Intuition

How it works

Why it works

Operations

Recognition

Interactive demo

Pseudocode

Implementation

Complexity

Advantages & disadvantages

Use cases

Alternatives

Common mistakes

Interview patterns

Interview problems

Related