Skip to content
Back to Data StructuresAll lessons

Data Structures

Adjacency Matrix

Check if two specific nodes are connected: O(1), one cell lookup · Find all neighbors of a node: O(n), scanning its row · Space: O(n^2), even if there are very few actual connections.

The idea, in plain English

An adjacency matrix is like a friendship spreadsheet. Write everyone's name across the top and down the side. To check if two people are friends, find the cell where their row and column meet. A 1 means friends, a 0 means not. It's the same map of connections as an adjacency list, just stored as a grid instead of a phone book.

How it works

  1. 1Make an N x N grid of zeros, one row and one column per node (N = number of nodes).
  2. 2To connect node A and node B, set grid[A][B] = 1 (and grid[B][A] = 1 too, if the connection goes both ways).
  3. 3To check if two nodes are connected, just read one cell, grid[A][B] — no searching needed.
  4. 4To find all of a node's neighbors, scan its whole row and collect every column that's a 1.

When you'd use it

Use an adjacency matrix for dense graphs, where most pairs of nodes are connected. Also use it whenever 'are A and B connected?' needs to be instant, and extra memory isn't a problem.

Common beginner mistakes

  • Don't use an adjacency matrix for a huge, sparse graph with few actual connections. You'd allocate n^2 cells to store only a handful of 1s. An adjacency list is far lighter there.
  • Remember to mirror the update for an undirected graph. If you set grid[A][B] = 1 without also setting grid[B][A] = 1, the connection is only 'visible' from one side.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Amy-Bo connected: yes
Amy-Dee connected: no
Amy's friends: Bo, Cy
Dee's friends: Bo

See it in motion

Graph ↔ gridAdjacency matrix · 4×4Check if two specific nodes are connected: O(1), one cell lookup · Find all neighbors of a node: O(n), scanning its row · Space: O(n^2), even if there are very few actual connections.

Ready. Press play — add edges to light the grid, then scan a row to read a node's neighbors.

4
Nodes
0
Edges
—
Row degree
0/7
Step
Adding edge / scanned nodeNeighbor (a 1 in the row)Existing edge (1)No edge (0)

Not sure this is the right topic? See the learning paths → or where this leads →