AntInLoop

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.

OperationComplexity
AccessO(1)
SearchO(1) edge check / O(V) neighbors
InsertionO(1)
DeletionO(1)
SpaceO(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