Adjacency Matrix Graph Representation Data Structure
An Adjacency Matrix stores a graph as a V x V grid where entry (u, v) holds the edge indicator or weight, giving O(1) edge lookups and powering Floyd–Warshall and matrix walk counting.
| Operation | Complexity |
|---|---|
| Access | O(1) |
| Search | O(1) edge check / O(V) neighbors |
| Insertion | O(1) |
| Deletion | O(1) |
| Space | O(V^2) |
Interactive Visualizer · C++ / Python / Java / JS Code
Adjacency Matrix Graph Representation
An Adjacency Matrix represents a $V$-vertex graph as a $V \times V$ 2D array M where M[u][v] is 1 (or edge weight w) if edge (u, v) exists and 0 (or INF) otherwise. For an undirected graph, M is symmetric (M[u][v] == M[v][u]). It provides instant $O(1)$ edge queries and direct algebraic power (M^k counts walks of length k!), at the cost of $O(V^2)$ space.
At a Glance
| Operation | Complexity |
| :--- | :---: |
| Memory | $O(V^2)$ (or $O(V^2 / 64)$ words with std::bitset) |
| Check / Add / Remove Edge (u, v) | $O(1)$ |
| Iterate All Neighbors of u | $O(V)$ |
---
Practice Problems
Easy
1. Count Triangles in an Undirected Graph Using std::bitset Rows ($O(V^3 / 64)$)
Given a dense undirected graph as an adjacency matrix, count all triangles $(u, v, w)$ in $O(V^3 / 64)$ time!
Approach: Store each row adj[u] as a std::bitset. For every edge (u, v) with u < v, (adj[u] & adj[v]).count() counts all common neighbors w in $O(V / 64)$ bitwise CPU instructions! Divide the total by 3.
<details>
<summary>Show C++ Solution</summary>
#include <bitset>
#include <iostream>
#include <vector>
constexpr int MAXV = 64;
int main() {
int n = 4;
std::vector<std::bitset<MAXV>> mat(n);
auto addEdge = [&](int u, int v) { mat[u][v] = mat[v][u] = 1; };
addEdge(0, 1); addEdge(1, 2); addEdge(2, 0); addEdge(1, 3); addEdge(2, 3);
long long total = 0;
for (int u = 0; u < n; ++u) {
for (int v = u + 1; v < n; ++v) {
if (mat[u][v]) total += (mat[u] & mat[v]).count();
}
}
std::cout << "Triangles: " << (total / 3) << "\n"; // 2
return 0;
}
</details>
2. Find the Universal Sink (Celebrity Problem) in $O(V)$ Time
In a directed graph given as an adjacency matrix, a universal sink has in-degree V - 1 and out-degree 0. Find it in $O(V)$ time (without even reading all $V^2$ cells!).
Approach: Start with candidate cand = 0. For i = 1..V-1, if mat[cand][i] == 1, cand cannot be a sink → cand = i; else i cannot be a sink! Finally verify cand's row is all 0s and its column (except [cand][cand]) is all 1s. Time: $O(V)$!
<details>
<summary>Show C++ Solution</summary>
#include <iostream>
#include <vector>
int findUniversalSink(const std::vector<std::vector<int>>& mat) {
int n = static_cast<int>(mat.size()), cand = 0;
for (int i = 1; i < n; ++i) {
if (mat[cand][i] == 1) cand = i;
}
for (int i = 0; i < n; ++i) {
if (i == cand) continue;
if (mat[cand][i] == 1 || mat[i][cand] == 0) return -1;
}
return cand;
}
int main() {
std::vector<std::vector<int>> mat = {
{0, 1, 1, 0},
{0, 0, 1, 0},
{0, 0, 0, 0},
{1, 0, 1, 0}
};
std::cout << "Universal sink: " << findUniversalSink(mat) << "\n"; // 2
return 0;
}
</details>
---
Related Structures & Algorithms
- Adjacency List — $O(V + E)$ alternative for sparse graphs.
- Floyd–Warshall Algorithm — operates directly on a $V \times V$ Adjacency Matrix.