Graph Adjacency Matrix Explained Tutorial

What Is a Graph Adjacency Matrix?

An adjacency matrix is a two-dimensional array used to represent the connections between vertices in a graph. Each row and column represents a vertex, and the value at a particular row and column indicates whether an edge exists between those two vertices.

Adjacency matrices are especially useful when a graph has a relatively large number of edges and you need to check whether a direct connection exists between two vertices quickly.

Basic Structure

Suppose a graph contains four vertices: A, B, C, and D. We can create a matrix where both the rows and columns represent these vertices.

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

A value of 1 indicates that an edge exists, while 0 indicates that there is no edge. The exact values used can vary depending on the implementation.

How the Matrix Represents Edges

If the matrix contains a value of 1 at row A and column B, there is an edge from A to B or a connection between A and B, depending on whether the graph is directed or undirected.

In this example, A is connected to B, and B is connected to C. There is no direct edge between A and C.

Adjacency Matrix for an Undirected Graph

In an undirected graph, an edge connects two vertices in both directions. Therefore, the adjacency matrix is normally symmetric around its main diagonal.

Because A-B is an edge, both matrix[A][B] and matrix[B][A] contain 1.

Adding an Undirected Edge

matrix[A][B] = 1;
matrix[B][A] = 1;

Both positions must be updated because the connection works in both directions.

Adjacency Matrix for a Directed Graph

In a directed graph, edges have a specific direction. Therefore, the matrix does not have to be symmetric.

This represents A → B and B → C. There is no edge from B → A or C → B.

Adding a Directed Edge

matrix[A][B] = 1;

Only the source-to-destination position is updated. If B → A is also required, it must be represented separately.

Creating an Adjacency Matrix in JavaScript

A JavaScript array can be used to create the two-dimensional structure required for an adjacency matrix.

const vertices = ['A', 'B', 'C', 'D'];

const matrix = Array.from(
  { length: vertices.length },
  () => Array(vertices.length).fill(0)
);

console.log(matrix);

This creates a square matrix containing one row and one column for every vertex.

Building an Undirected Graph

A graph class can maintain both the list of vertices and the adjacency matrix. When an undirected edge is added, both corresponding matrix positions are updated.

class Graph {
  constructor(size) {
    this.matrix = Array.from(
      { length: size },
      () => Array(size).fill(0)
    );
  }

  addEdge(a, b) {
    this.matrix[a][b] = 1;
    this.matrix[b][a] = 1;
  }
}

const graph = new Graph(4);

graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);

console.log(graph.matrix);

Building a Directed Graph

A directed graph uses the same matrix structure, but an edge changes only the source row and destination column.

class DirectedGraph {
  constructor(size) {
    this.matrix = Array.from(
      { length: size },
      () => Array(size).fill(0)
    );
  }

  addEdge(from, to) {
    this.matrix[from][to] = 1;
  }
}

const graph = new DirectedGraph(4);

graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 3);

console.log(graph.matrix);

Adding and Removing Edges

One advantage of an adjacency matrix is that adding or removing an edge does not require searching through a list of neighbors.

Undirected Graph

// Add edge
matrix[a][b] = 1;
matrix[b][a] = 1;

// Remove edge
matrix[a][b] = 0;
matrix[b][a] = 0;

Directed Graph

// Add edge
matrix[from][to] = 1;

// Remove edge
matrix[from][to] = 0;

Checking Whether an Edge Exists

Checking whether two vertices have a direct connection is one of the strongest use cases for an adjacency matrix.

function hasEdge(matrix, from, to) {
  return matrix[from][to] === 1;
}

console.log(hasEdge(matrix, 0, 1));

The matrix provides direct access to the required cell, so this operation takes O(1) time.

Finding the Neighbors of a Vertex

To find all neighbors of a vertex, scan the corresponding row of the matrix.

function getNeighbors(matrix, vertex) {
  const neighbors = [];

  for (let i = 0; i < matrix[vertex].length; i++) {
    if (matrix[vertex][i] === 1) {
      neighbors.push(i);
    }
  }

  return neighbors;
}

console.log(getNeighbors(matrix, 0));

Finding all neighbors requires scanning the row, so the operation takes O(V) time where V is the number of vertices.

Weighted Adjacency Matrix

An adjacency matrix can also represent a weighted graph. Instead of storing only 0 and 1, the matrix stores the edge weight.

    A  B  C
A   0  4  10
B   4  0  3
C   10 3  0

The value 4 means that the edge between A and B has weight 4, while the value 10 represents the weight between A and C.

A special value such as Infinity can be used to represent the absence of an edge when zero is a valid edge weight.

const matrix = [
  [0, 4, 10],
  [4, 0, 3],
  [10, 3, 0]
];

Self-Loops

A self-loop is an edge from a vertex to itself. In an adjacency matrix, it is represented on the main diagonal.

The value at matrix[A][A] represents the self-loop on A. Whether self-loops are allowed depends on the graph model.

Adjacency Matrix and Graph Traversal

BFS and DFS can both operate on graphs represented by adjacency matrices. The main difference from an adjacency list is that finding neighbors requires scanning a complete matrix row.

BFS with an Adjacency Matrix

function bfs(matrix, start) {
  const visited = new Set();
  const queue = [start];

  visited.add(start);

  while (queue.length > 0) {
    const current = queue.shift();

    console.log(current);

    for (let neighbor = 0; neighbor < matrix.length; neighbor++) {
      if (matrix[current][neighbor] === 1 && !visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

For an adjacency matrix, BFS or DFS generally takes O(V²) time because each visited vertex may require scanning an entire row.

Space Complexity

An adjacency matrix always allocates space for every possible pair of vertices.

For V vertices, the matrix contains V × V entries.

Therefore, the space complexity is:

Space: O(V²)

This can become expensive when the graph contains many vertices but relatively few edges.

Time Complexity of Common Operations

Operation	Time Complexity	Reason
Check edge	O(1)	Direct matrix access
Add edge	O(1)	Direct cell update
Remove edge	O(1)	Direct cell update
Find neighbors	O(V)	Scan one matrix row
BFS / DFS	O(V²)	Rows are scanned during traversal
Space	O(V²)	V × V matrix entries

Adjacency Matrix vs Adjacency List

An adjacency matrix and adjacency list represent the same graph in different ways. The right choice depends on the graph size, density, and operations required.

Feature	Adjacency Matrix	Adjacency List
Space	O(V²)	O(V + E)
Check edge	O(1)	Typically O(degree) without an auxiliary lookup structure
Find neighbors	O(V)	O(degree)
Best suited for	Dense graphs and frequent edge lookups	Sparse graphs and traversal-heavy operations

When Should You Use an Adjacency Matrix?

An adjacency matrix is useful when the number of vertices is manageable and the graph is relatively dense or the application frequently asks whether a specific edge exists.

You need constant-time direct edge lookup.
The graph is dense and contains many edges.
The number of vertices is known and reasonably bounded.
You need a simple representation for mathematical graph operations.
You frequently update or inspect specific vertex pairs.

When an Adjacency Matrix May Be Inefficient

A matrix stores space for every possible vertex pair, even when no edge exists. This can waste significant memory for sparse graphs.

1000 vertices
10 actual edges

A matrix still needs approximately one million cells for 1,000 vertices, even though only a small number of connections exist. An adjacency list can store the actual connections much more compactly.

Practical Example: City Connections

Consider a graph where each vertex represents a city and an edge means that a direct route exists between two cities.

const cities = ['Hyderabad', 'Mumbai', 'Delhi', 'Chennai'];

const matrix = [
  [0, 1, 0, 1],
  [1, 0, 1, 0],
  [0, 1, 0, 1],
  [1, 0, 1, 0]
];

For example, matrix[0][1] being 1 indicates a direct connection between Hyderabad and Mumbai in this simplified undirected model.

Common Mistakes

Forgetting that rows and columns must use the same vertex ordering.
Updating only one matrix cell when adding an undirected edge.
Accidentally adding a reverse edge to a directed graph.
Using 0 as the "no edge" value when zero is a valid weight.
Forgetting that an adjacency matrix requires O(V²) memory.
Assuming finding neighbors is O(1); the row normally has to be scanned.
Using an adjacency matrix for a very large sparse graph without considering memory usage.

Key Takeaways

An adjacency matrix is a V × V two-dimensional representation of a graph.
Rows and columns represent vertices.
A matrix cell represents the relationship between a pair of vertices.
Undirected graph matrices are normally symmetric.
Directed graph matrices do not have to be symmetric.
Weighted graphs can store edge weights instead of simple 0/1 values.
Checking for a direct edge takes O(1) time.
Finding all neighbors takes O(V) time.
The matrix requires O(V²) space.
Adjacency matrices are particularly useful for dense graphs and frequent edge lookups.

Topics

Graph Adjacency Matrix Explained