Graph Representation

Adjacency Matrix

What is an Adjacency Matrix?

An adjacency matrix represents a graph as a 2D grid: a V×V table where V is the number of vertices. The cell at row i, column j holds a nonzero value (often just 1, or an edge's weight) if there's an edge from vertex i to vertex j, and 0 otherwise. For an undirected graph, an edge sets both cell (i, j) and cell (j, i), so the matrix is symmetric across its diagonal; for a directed graph, only the one cell matching the edge's direction is set.

How Does It Work?

The main advantage is speed for a very specific question: "is there an edge between these two vertices?" Checking cell (i, j) is a single array lookup — O(1) — regardless of how many edges the graph has. Iterating over all of a vertex's neighbors, though, means scanning an entire row, which costs O(V) even if that vertex only has one or two actual edges.

That scanning cost is what makes adjacency matrices a poor fit for sparse graphs — graphs where the number of edges is much smaller than V². A social network with millions of users but only a few hundred friends each would waste almost the entire matrix on zeros, both in memory (O(V²) regardless of edge count) and in wasted iteration time. Adjacency lists exist specifically to fix this by only storing the edges that actually exist.

An undirected triangle graph — its matrix is symmetric, and the diagonal stays 0 (no self-loops)

	A	B	C
A	0	1	1
B	1	0	1
C	1	1	0

Building the Matrix

Create a V×V grid, initialized to all zeros
For every edge (u, v) with weight w: set matrix[u][v] = w
If the graph is undirected, also set matrix[v][u] = w — the same edge is recorded from both directions
To check if an edge exists between two vertices, read matrix[u][v] directly

Complexity

Space Complexity: O(V²) — regardless of how many edges actually exist.
Check if edge (u, v) exists: O(1) — a single cell lookup.
Iterate over a vertex's neighbors: O(V) — the entire row must be scanned.
Add or remove an edge: O(1) — updating a single (or mirrored pair of) cells.

Time Complexity Analysis

Adjacency matrices earn their keep on dense graphs (where edges approach V²), in algorithms that need fast edge-existence checks (like Floyd-Warshall's all-pairs shortest paths, which is naturally matrix-based), and in small, fixed-size graphs where the O(V²) memory cost is negligible and the O(1) lookup is worth it.

Daily DSA Challenge by Scale Engineer

See how a graph's edges become entries in its adjacency matrix

Directed graph

Add vertices, then connect them with edges

Graph

Add a vertex to begin

Adjacency Matrix

Add vertices to see the matrix

Edge existsMost recently set edgeSelected cell (click any cell)

Test Your Knowledge before moving forward!

Adjacency Matrix Quiz

How it works:

+1 point for each correct answer
0 points for wrong answers
-0.5 point penalty for viewing explanations
Earn stars based on your final score (max 5 stars)

Adjacency Matrix Implementation

class GraphMatrix {
  constructor(vertices) {
    this.vertices = vertices; // e.g. ["A", "B", "C"]
    this.index = Object.fromEntries(vertices.map((v, i) => [v, i]));
    this.matrix = Array.from({ length: vertices.length }, () => Array(vertices.length).fill(0));
  }

  addEdge(from, to, weight = 1, directed = false) {
    const i = this.index[from];
    const j = this.index[to];
    this.matrix[i][j] = weight;
    if (!directed) this.matrix[j][i] = weight; // mirror the edge both ways
  }

  hasEdge(from, to) {
    return this.matrix[this.index[from]][this.index[to]] !== 0; // O(1) lookup
  }

  neighbors(vertex) {
    const i = this.index[vertex];
    return this.vertices.filter((_, j) => this.matrix[i][j] !== 0); // O(V) scan
  }
}

// Usage example
const g = new GraphMatrix(["A", "B", "C", "D"]);
g.addEdge("A", "B");
g.addEdge("A", "C");
g.hasEdge("A", "B"); // true
g.neighbors("A");    // ["B", "C"]

Done With the Learning

Mark Adjacency Matrix as done and view it on your dashboard

Explore Other Topics

Adjacency List

Binary Search

Structure & Properties

Heap Sort