I recently saw a really interesting implementation of graphs that were really simple and not that complicated to use, figuring itβd be the perfect blog tutorial. Credit where credit is due, I got this from one of fireshipβs awesome videos. If you havenβt already stumbled across the great content of his, check it out right here. Now off to the races!

First off, graphs typically are saved in two different ways. The first as a list of pairs that demonstrate either the single or bidirectional paths between nodes. This first type is known as an Adjacency List. Whereas the second form makes use of a matrix, or two dimensional array where each (i,j) location in the matrix has a value (typically 1 or 0, inferring connection or none present, respectively)

## Adjacency Lists

Without having to mess with any classes or OOP, we can kick start our list by using just some functional programming. First we list out the nodes we want in our graph with:

```
const nodes = [0,1,2,3,4,5,6,7]
```

Where each element in this array stands for a node in the graph. Remember that this array can hold any sort of element, like strings for airport codes (what fireship uses), names for actors, user objects, whatever.

Now we can save our edges as a two dimensional array where each element represents a linked edge between the nodes, as in:

```
const edges = [
[0,1],
[1,2],
[2,3],
[1,3],
[4,5],
[1,5],
[1,6],
[1,7]
]
```

These arenβt necessarily make up our list but theyβre instrumental in creating it.

Fireship uses ES6βs native map data structure to store his adjacency list as a collection of key object pairs.

```
const list = new Map()
```

Weβll add nodes onto our adjacency list by using βlist.add(β¦)β

```
const addNode = (node) => {
list.set(node,[])
}
```

Because a single node can point to several different other nodes, itβs important that we initialize each node key with an array that weβll push onto with each subsequent addition of an edge.

```
const addEdge = (start, end) => {
list.get(start).push(end)
list.get(end).push(start)
}
```

This is supposing that the graph is bidirectional, and a single directional graph would only push onto the starting nodes array of connections.

All together, a graph creation method would look like

```
const createGraph = (nodes, edges) => {
nodes.forEach(node => addNode(node))
edges.forEach(edge => addEdge(edge[0],edge[1]))
}
```

I was amazed at the simplicity of fireshipβs implementation, before being sort of daunted with the setup of a graph. This seems to be a very slim implementation of a graph.

## Adjacency Matrix

In the format we have, where nodes are referenced as ordered digits starting at 0, we can create a pretty good representation of a two dimensional array with some methods like the above.

Weβll start with an empty array like so

```
const matrix = []
```

And use the same sort of node and edges variables defined above.

Adding a node will simply look like

```
const addNode = (node) => {
for (let i = 0; i < matrix.length; i++) {
const col = matrix[i]
col.push(0)
}
matrix.push(new Array(matrix.length).fill(0))
}
```

Every addition of the node will mean an added column and added row. So we need to push an array onto the end of our matrix array that will hold all the connections of that ith column node as well as add an extra index onto all existing columns of the matrix. This means O(n) time for a matrix of size nxn.

Adding edges is more straight forward as seen here

```
const addEdge = (start,end) => {
matrix[start][end] = 1;
matrix[end][start] = 1
}
```

Again, this is a bidirectional graph where locations in our matrix marked with a zero mean no connection and 1 means connection. We could easily initialize a weighted graph where values can be greater than one to model something like street or flight paths.

We can finally initialize our graph with this method

```
const createGraph = (nodes,edges) => {
nodes.forEach(node => addNode(node))
edges.forEach(edge => addEdge(edge[0],edge[1]))
}
```

Pretty much exactly mirroring our adjacency list implementation.

## Top comments (0)