Chapter 66

Home

Graph Representation: Adjacency Matrix

An adjacency matrix is a V×V table where cell [u][v] = 1 if edge u→v exists, or the edge weight for weighted graphs. O(1) edge queries, but O(V²) memory.

When to Use an Adjacency Matrix

Use it when V ≤ 1000 and you need frequent edge-existence checks. For V ≤ 100, it's simpler and faster than an adjacency list. For V ≥ 10⁴, O(V²) memory is prohibitive (100M entries for V=10⁴).

C++

int V = 5;
vector> mat(V, vector(V, 0));

// Add edge u→v
mat[u][v] = 1;  // or weight for weighted

// Check edge existence
if (mat[u][v]) { /* edge exists */ }

// Floyd-Warshall uses this

Rust

let v = 5;
let mut mat = vec![vec![0; v]; v];
mat[u][v] = 1;

📐 Comparison

Adj list: O(V+E) memory, O(deg(u)) to iterate neighbours. Adj matrix: O(V²) memory, O(V) to iterate neighbours, but O(1) edge query.

Key Takeaways

Practice