Representing a Weighted Graph with an Adjacency Matrix in JavaScript

Photo by Omar Flores on Unsplash

I recently came across an implementation of an undirected weighted graph using an adjacency matrix. Prior to this, I was used to seeing graphs represented using adjacency lists. To keep this blog focused, today I’ll only be writing about representing a weighted graph using an adjacency matrix, and will assume that the reader is already aware of how to represent a graph using an adjacency list. By the end of this blog, the goal will be that you will be able to build a Graph class which utilizes an adjacency matrix.

What is an Adjacency Matrix?

Square Matrix

An adjacency matrix, is a square matrix which is used to represent the edges of a graph. A square matrix is a two-dimensional array, an array which contains arrays all of equal size to itself. For example:

[[0,0,0]
 [0,0,0]
 [0,0,0]]

The main array contains 3 arrays, which also have a length of 3. This is a square matrix.

Adjacency Matrix

So to represent a graph as an adjacency matrix, we will use the intersections of the columns and rows to represent an edge. For an unweighted graph, that intersection will just have a value of 1 to represent an edge between two vertices. For a weighted graph, we will simply put the weight as the value at that intersection. Let’s take this undirected, weighted graph:

First let’s just look at it represented as a grid, so you can see what I mean when I say ‘column’ and ‘row’.

  A B C D
A 0 2 3 0
B 2 0 0 2
C 3 0 0 6
D 0 2 6 0

Now, as an actual matrix:

[[0, 2, 3, 0],
 [2, 0, 0, 2],
 [3, 0, 0, 6],
 [0, 2, 6, 0]]

You can see an undirected graph will be symmetrical across the top left to bottom right diagonal. Which means, if we have two vertices, i and j, which are connected by an edge, that means matrix[i][j] will be equal to matrix[j][i].

Code

Let’s start with our class constructor.

From now on, all code will go inside this class body.

We will initialize it with the size of our prospective graph. Remember, the size of your graph should be the number of vertices in your graph.

Now we need to be able to:

• Add a vertex
• Remove a vertex
• Add an edge
• Remove an edge
• Print our adjacency matrix

Let’s start by adding an edge, assuming that we will have initialized our graph with enough space to accommodate for all of our vertices.

Our vertices are represented by the indices of our matrix. So, we just need to check that neither go outside the bounds of our matrix, and that they are not the same vertex. After that we just assign this.matrix[vertex1][vertex2] and this.matrix[vertex2][vertex1] to the weight.

Removing an edge is very similar.

We check that the vertices are valid, and if so we just reset them to 0.

Now we need to be able to add a vertex to our matrix.

First we increase our size, then we push an empty array into our matrix. We need to add a 0 into the previously existing arrays, and at the same time fill our new array with 0s.

Now we can add a vertex, so we need to be able to remove a vertex.

This is where things get a little more complicated. First we check the validity of the vertex given (has to be within the bounds of the matrix). Then, we need to shift every element in each row left by 1, over writing the vertex we are removing. This takes care of our rows! We also need to shift every element up by one, over writing the column which represents our vertex. Finally we pop off the empty array, and decrease our size.

Now we just need to print our adjacency matrix.

Nice and simple. Very similar to how we initialize our adjacency matrix. We just go row by row, adding each element to a string to be printed out!

In Conclusion…

When I first saw a graph represented by an adjacency matrix, I was intimidated. It wasn’t too hard to understand once I started coding. I found the fact that it was undirected actually made things more simple. Using an adjacency matrix takes up a lot more space than just using an adjacency list, especially if your edges are sparse. However, it has the benefit of constant lookup to see if there is an edge between two vertices. Nonetheless I’m glad I now know both of the most common ways to represent a graph in JavaScript!