Adjacency Matrix: Operations and Complexity
What You'll Learn
You'll learn how fast (or slow) basic graph operations are when using an adjacency matrix representation.
Core Operations and Their Complexity
An adjacency matrix stores graph edges in a 2D array. Let's analyze how efficiently it handles three fundamental operations for a graph with n vertices.
Edge Insertion
Adding an edge from vertex u to vertex v:
- Set
matrix[u][v] = 1(or the edge weight) - For undirected graphs, also set
matrix[v][u] = 1
Time Complexity: O(1) — constant time! You directly access the array position and update it. It's like flipping a light switch; you know exactly where it is.
Edge Deletion
Removing an edge between vertices u and v:
- Set
matrix[u][v] = 0 - For undirected graphs, also set
matrix[v][u] = 0
Time Complexity: O(1) — again, direct array access makes this instant.
Edge Lookup (Query)
Checking if edge (u, v) exists:
- Return
matrix[u][v](check if it's non-zero)
Time Complexity: O(1) — just read one cell in the matrix.
The Trade-off
While adjacency matrices excel at edge operations, they use O(n²) space regardless of how many edges actually exist. Finding all neighbors of a vertex requires scanning an entire row, taking O(n) time even if the vertex has only one neighbor.
Think of it like a seating chart for n people: checking if two specific people sit together is instant (lookup), adding or removing a seating assignment is instant (insertion/deletion), but listing everyone sitting next to one person means checking all n seats (neighbor enumeration).
Key Takeaway: Adjacency matrices provide O(1) edge insertion, deletion, and lookup, making them ideal for dense graphs where fast edge queries matter, despite their O(n²) space cost.