# Adjacency Matrix

An Adjacency Matrix is a useful mean of representating adjacency between the vertices of a graph.

## Building an Adjacency Matrix

Given a graph **G** with **n** vertices and **m** edges the adjacency matrix is constructed using an \( n \times n \) matrix like this one:

And each element represents the value of the edge that connects two vertices.

There are some rules you must follow when constructing an adjacency matrix:

The value \( a_{i,j} \) is equal to the value \( v \) of the weight of the edge that connects the vertex \(i \) and the vertex \( j \) . If the graph is undirected \( a_{i,j}=a_{j,i} \) .

If the vertices \( i \) and \(j\) are not connected \( a_{i,j}= \infty \) or \( a_{i,j} = 0 \). (It depends on the kind of problem you are working with, in some cases using 0 is ok, whilst in others it's not ok (e.g graphs that have negative edges) in this case, you must use \( \infty\) ).

If \( i=j \), \( a_{i,j}= \infty \) or \( a_{i,j}= 0 \).

## Example Question 1

Create an adjacency matrix for the following graph:

The graph is undirected, so we can conclude that \( a_{i,j} = a_{j,i} \) for every \( i \) and \( j \).

We know that if \( i \) and \( j \) are not linked by an edge or if \( i = j \), \( a_{i,j}=\infty \), then:

Now we just have to complete the matrix identifying the weight of each edge and which vertices are connected by it. Finally we get:

## Adjacency Matrix vs Adjacency Lists

An adjacency list is a series of unordered lists. There is one list for every node in the graph, and the list contains all the connected nodes to the current node.

The adjacency matrix uses a constant \(O(n^2)\) space, no matter how many connected edges there are. This is more efficient for denser graphs, which refers to graphs that has more edges.

The space complexity for Adjacency list linear to the number of edges in the graph. It is more efficient when the graph is sparse, meaning that there are fewer nodes.

**Cite as:**Adjacency Matrix.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/adjacency-matrix/