# 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);  }}`

# 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']`

# 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.

## More from Ziyo Shams

Full Stack Developer