Adjacency matrix

An adjacency matrix is a $V \times V$ boolean matrix that represents a Graph. Entry $A_{i, j}$ is $1$ if there’s an edge from vertex $v_{i}$ to vertex $v_{j}$ , and $0$ otherwise.

$A_{i, j} = {10 (v_{i}, v_{j}) \in E otherwise$

For weighted graphs, $A_{i, j}$ holds the edge weight (with $\infty$ or $0$ used as a sentinel for “no edge,” depending on the algorithm’s needs).

Properties

Size: $V \times V$ regardless of edge count. If you have 1000 vertices and 5 edges, the matrix is still 1,000,000 entries.
Symmetric for undirected graphs: $A_{i, j} = A_{j, i}$ since edges go both ways.
Asymmetric for directed graphs: $A_{i, j} = 1$ doesn’t imply $A_{j, i} = 1$ .
Diagonal: $A_{i, i}$ represents a self-loop (an edge from a vertex to itself). Usually 0 in graphs without self-loops.

Operations

Operation	Complexity
Check if edge $(i, j)$ exists	$O (1)$
Add edge	$O (1)$
Remove edge	$O (1)$
Iterate all neighbors of $v$	$O (V)$
Total space	$O (V^{2})$

The killer feature is constant-time edge lookup — you index directly into the matrix. The cost is the $O (V^{2})$ space.

Implementation

A 2D array, typically:

int adj[MAX_V][MAX_V] = {0};   // initially all zeros
 
void addEdge(int u, int v, bool directed) {
    adj[u][v] = 1;
    if (!directed) adj[v][u] = 1;
}
 
bool hasEdge(int u, int v) {
    return adj[u][v] == 1;
}

For weighted graphs, replace int adj[][] with weights, and use a sentinel like INT_MAX to mean “no edge.”

When to use

Adjacency matrices win when:

The graph is dense — $E \approx V^{2}$ . The matrix isn’t wasting space because most cells are full.
Edge lookup is frequent and order-independent. $O (1)$ matters when you check edges constantly.
The graph is small — say, 100 vertices. The $V^{2} = 10, 000$ cells are negligible.
You need matrix operations: graph algorithms based on matrix multiplication (transitive closure via boolean matrix powers, BFS via matrix-vector products) work directly on adjacency matrices.

When not to use

Sparse graphs — most real-world graphs have $E ≪ V^{2}$ . A social network with millions of users and dozens of friends each is over 99% empty in matrix form.
Memory-constrained scenarios — large $V$ makes $V^{2}$ prohibitive.

In these cases, see Adjacency list.

Effect on algorithms

BFS and DFS both run in $O (V^{2})$ on an adjacency matrix — for each vertex, you scan all $V$ possible neighbors. With an adjacency list, the same algorithms run in $O (V + E)$ .

Some algorithms naturally work better with one representation:

Dijkstra on dense graphs: matrix is fine.
BFS/DFS on social networks: list is much better.
Floyd-Warshall (all-pairs shortest paths): matrix-based, $O (V^{3})$ regardless of $E$ .

For the alternative representation that scales to sparse graphs, see Adjacency list. For graph fundamentals, see Graph.

Idriss Rami — Notes

Explorer