Implementing Graphs with NodeJS and Javascript

Graphs in JavaScript with adjacency lists: modeling, neighbors, and a solid setup for BFS and DFS. Working Node.js code.

Modeling “who connects to whom” with nested objects turns into spaghetti — social graphs, recommendations, and routes need a graph. This episode builds an adjacency list in JavaScript, groundwork for BFS/DFS in ep. 14.

What you'll learn:

Directed vs undirected graphs (and weighted edges)
Vertices and neighbors in JS
Adjacency list vs adjacency matrix
Product examples: network, maps, recommendations

Prerequisites: trees (ep. 6) and the series overview.

Graphs in JavaScript: adjacency lists

Graphs are an essential data structure that allows us to represent complex relationships between elements, such as social networks, navigation systems and route optimization. Here we will cover the basics with implementation and a few concepts of graphs in NodeJS/JavaScript.

Image that represents a post about data structures in a nutshell implementing graphs with nodejs and javascript

Hands-on

First The Theory

Here you will remember about trees because the graph is a collection of nodes (or vertices) and edges, the edges are the ones that connect these nodes. Graphs can be directed or undirected and can include edges with weights (or other type of information), and when we have that, usually means that the edge has a cost or distance between nodes, and the cost should be considered when navigating through the graph... yes it kind of get a little bit more complex but let's try to simplify this here.

Now The Practice

So, let's dive in the code, the following is a basic graph structure, I mean, what a basic graph should have? It should have its nodes, and it's size:

code

class Graph {
  constructor() {
    this.numberOfNodes = 0
    this.adjacentList = {}
  }
}

Sooo that's it, graph is done, let's all go to sleep...I'm kidding, lets add some functions to insert and show the graph connections:

code

class Graph {
  constructor() {
    this.numberOfNodes = 0
    this.adjacentList = {}
  }
  add(node) {
    this.adjacentList[node] = []
    this.numberOfNodes++
  }
  addEdge(node1, node2) {
    this.adjacentList[node1].push(node2)
    this.adjacentList[node2].push(node1)
  }
  showConnections() {
    const all = Object.keys(this.adjacentList)
    for (let node of all) {
      let nodeConnections = this.adjacentList[node]
      let connections = ''
      let vertex
      for (vertex of nodeConnections) {
        connections += vertex + ' '
      }
      console.log(`${node} --> ${connections}`)
    }
  }
}

Let me explain each section:

code

add(node) {
    this.adjacentList[node] = [];
    this.numberOfNodes++;
}

On the above code the goal is to add items (or nodes) into the graph, but bear in mind that the variable where we are inserting data it's named as adjacentList but it's an object, I know that's a little confunsing now, but the intention here is to keep the names easy for you to identify in other places. So we are adding an object, and when we do adjacentList[node] = [] we are creating a object key inside the adjacentList object, and this key has an empty ([]) value, meaning that it has empty relations/connections.

code

 addEdge(node1, node2) {
    this.adjacentList[node1].push(node2);
    this.adjacentList[node2].push(node1);
}

When we add an Edge we basically are adding a connection between two nodes like a connection between X and Y. That's why we add both ways on the code, we need to add a connection from X to Y and another connection grom Y to X.

We do that because of the type of the graph we are creating is not a directional graph (thats a matter for another post) but keep in mind that we are basically creating a connection that comes and goes from 2 points (like a street). We can also note that in this basic template we are not adding any "weight" to the edges, if we wanna to do that (like in a graph that represents a street and the lenght of the street for instance) we could add the weight doing something like this:

code

addEdge(node1, node2, weight = 0) {
    this.addVertex(node1);
    this.addVertex(node2);
    this.vertices[node1].push({ node: node2, weight });
    this.vertices[node2].push({ node: node1, weight });
}

Of course this is a basic example, but I think you are starting to get the idea. Let's run some tests on the graph:

code

const myGraph = new Graph()
myGraph.add(0)
myGraph.add(1)
myGraph.add(2)
myGraph.add(3)
myGraph.addEdge(0, 2)
myGraph.addEdge(1, 2)
myGraph.addEdge(1, 3)
myGraph.addEdge(2, 3)
myGraph.showConnections()

If you did it right and tried to run the node file you should get something like this:

code

> node graph.js
0 --> 2
1 --> 2 3
2 --> 0 1 3
3 --> 1 2

To basically the showConnections function is saying that:

0 has a connection with 2.
1 has a connection with 2 and 3.
2 has a connection with 0, 1 and 3.
3 has a connection with 1 and 2.

Does this information triggers something in your brain?

example graph image

Edge cases: dense graphs and `shift` in BFS

Adjacency lists with Map + neighbor arrays suit sparse graphs. Near-complete graphs may be simpler as an adjacency matrix — O(V²) memory, O(1) edge lookup.

In ep. 14 you use queue.shift() for BFS — is that slow? Yes. shift() is O(n) on arrays. For large graphs use a head index or deque; the algorithm stays the same.