# What Is Adjacency Matrix Data Structure?

//

Larry Thompson

The adjacency matrix data structure is a fundamental concept in graph theory. It represents the connections between vertices in a graph using a two-dimensional matrix. Each row and column in the matrix corresponds to a vertex, and the value in each cell indicates whether there is an edge between the vertices.

## What is an Adjacency Matrix?

An adjacency matrix is a square matrix that represents a graph. The rows and columns of the matrix correspond to the vertices of the graph, and each cell indicates whether there is an edge between two vertices. If there is an edge, the cell value is typically set to 1 or true, and if there isn’t, it’s set to 0 or false.

Let’s consider an example:

```Vertices: A, B, C
Edges: (A,B), (B,C), (C,A)

A   B   C
------------
A |  0   1   1
B |  1   0   1
C |  1   1   0

```

In this example, we have three vertices A, B, and C. The edges are (A,B), (B,C), and (C,A). The adjacency matrix shows that there is an edge between A and B, B and C, as well as C and A.

• Simplicity: The concept of representing connections between vertices using a matrix is simple to understand.
• Efficient Edge Queries: Determining whether two vertices are connected is highly efficient with an adjacency matrix. Accessing a specific cell in the matrix takes constant time, O(1).
• Space Efficiency for Dense Graphs: If the graph has many edges, the adjacency matrix uses less space compared to other data structures like an adjacency list.