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.
Latest comments (0)