Adjacency Matrix

While an edge list won't end up being the most efficient choice, we can move beyond a list and implement a matrix. For many, a matrix is a significantly better kinesthetic representation for a graph.

An adjacency matrix is a matrix that represents exactly which vertices/nodes in a graph have edges between them. It serves as a lookup table, where a value of 1 represents an edge that exists and a 0 represents an edge that does not exist. The indices of the matrix model the nodes.

Once we've determined the two nodes that we want to find an edge between, we look at the value at the intersection of those two nodes to determine whether there's a link.

In this illustration, we can see that the adjacency matrix has a chain of cells with value 0 diagonally. In fact, this is true of most graphs that we'll deal with, as most won't be self-referential. In other words, since node 2 does not (or can not) have a link to itself, if we were to draw a line from column 2 to row 2, the value will be 0.

However, if we wanted to see if node 3 was connected to node 1, we'd find there to be a relationship. We could find column 3, row 1, and see that the value is 1, which means that there is an edge between these two nodes.

Adjacency matrices are easy to follow and represent. Looking up, inserting and removing an edge can all be done in O(1) or constant time. However, they do have a downfall, which is that they can take up more space than is necessary. An adjacency matrix always consumes O(V^2) (V being vertices) amount of space.

Nevertheless, adjacency matrices are definitely a step up from an edge list. Their representation would look like this:

xxxxxxxxxx

const matrix = [

  [0, 1, 1],

  [1, 0, 1],

  [1, 1, 0]

];