Graph Data Structure in JavaScript

Unfortunately there isn’t many sources for JavaScript when it comes to Data Structures. I have decided to share my knowledge about Graphs, so someone like you could find and learn from it. Firstly, I am assuming that you already have some idea about what Graphs are. I won’t bore you with the definition. Let’s get started with implementation.

Create an ES6 class

We will be implementing Directed Graph (Digraph) with Adjacency List. Also I will be using some ECMA2015+ syntax, which should not be difficult to understand.

Add basic Graph methods

Add Vertex method

addVertex(vertex) {
if (!this.AdjList.has(vertex)) {
this.AdjList.set(vertex, []);
} else {
throw 'Already Exist!!!';
}
}
let graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
Map {
'A' => [],
'B' => [],
'C' => [],
'D' => []
}
Map {
'A' => ['B', 'C', 'D'],
'B' => [],
'C' => ['B'],
'D' => ['C']
}

Add Edge method

addEdge(vertex, node) {
if (this.AdjList.has(vertex)) {
if (this.AdjList.has(node)){
let arr = this.AdjList.get(vertex);
if(!arr.includes(node)){
arr.push(node);
}
}else {
throw `Can't add non-existing vertex ->'${node}'`;
}
} else {
throw `You should add '${vertex}' first`;
}
}

Add print method

This step is not necessary, but after adding vertices and edges we want to see if they are being added properly.

print() {
for (let [key, value] of this.AdjList) {
console.log(key, value);
}
}

Here is what you should have by now:

Let’s build a Graph

let g = new Graph();
let arr = ['A', 'B', 'C', 'D', 'E', 'F'];
for (let i = 0; i < arr.length; i++) {
g.addVertex(arr[i]);
}
g.addEdge('A', 'B');
g.addEdge('A', 'D');
g.addEdge('A', 'E');
g.addEdge('B', 'C');
g.addEdge('D', 'E');
g.addEdge('E', 'F');
g.addEdge('E', 'C');
g.addEdge('C', 'F');
g.print();
/* PRINTED */
// A [ 'B', 'D', 'E' ]
// B [ 'C' ]
// C [ 'F' ]
// D [ 'E' ]
// E [ 'F', 'C' ]
// F []

Breadth First Search (BFS)

BFS in Graphs is almost the same as in Binary Search Tree, but there is a little difference. The main difference is that you can have loops in Graphs. You have to keep track of the nodes that you visit. Here is how you do it:

  • initialize an empty object called visited .
  • initialize an empty array called q which will be used as a Queue.
  • mark the starting node as visited. ( visited = {'A': true} )
  • put the starting node in the queue. ( q = ['A'] )
  • loop until queue is empty
  • print current
  • get edges for current from the graph. (let arr = this.AdjList.get(current)). Lets say we popped A from the queue and got arr = ['B','D','E'] .
  • if element is not visited, mark each element as visited and put it in the queue.
visited = {
'A': true,
'B': true,
'D': true,
'E': true
}
q = ['B', 'D', 'E']

BFS method code snippet

Depth First Search (DFS)

This method will accept a starting node like BFS and keep track of visited nodes. We will implement this method recursively and the helper function will do the recursion. Here is how we do it:

  • Create visited object let visited = this.createVisitedObject() .
  • Call the helper function passing starting node and visited object this.dfsHelper(startingNode, visited) .
  • dfsHelper will mark it as visited and print it.

Does path exist method

The reason it is easy to implement this method is that it is almost identical to BFS method. You can use DFS to look for a path but it will not be optimal. For more information on this topic watch Gayle Laakmann McDowell, the author of Cracking The Coding Interview book. Since you already know what BFS is and how it works, I will leave the code here for you to analyze.

And here is a playground for you to play and test this code.

Full Stack Developer