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

In the `constructor`

we create a new instance of Map object and we call it `AdjList`

. (*If you are not comfortable with ***Maps*** use ***Object***, they are very similar. Example: *`this.AdjList = {}`

).

# Add basic Graph methods

## Add Vertex method

`addVertex(`*vertex*) {

if (!*this*.AdjList.has(vertex)) {

* this*.AdjList.set(vertex, []);

} else {

throw 'Already Exist!!!';

}

}

This method takes a vertex as an argument and adds it to the graph.

For example, create an *instance of the Graph* and add several *vertices*:

`let graph = new Graph();`

graph.addVertex('A');

graph.addVertex('B');

graph.addVertex('C');

graph.addVertex('D');

Now our `AdjList `

variable contains this:

`Map {`

'A' => [],

'B' => [],

'C' => [],

'D' => []

}

Why do we have **values** as an **empty array**? In that array we will be storing **edges**. Here is an illustration:

If we were to implement the graph on the illustration then our **Map** would look like this:

`Map {`

'A' => ['B', 'C', 'D'],

'B' => [],

'C' => ['B'],

'D' => ['C']

}

Let’s implement `addEdge`

method which will populate those empty arrays.

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

}

}

Before we add an **edge** to a **vertex**, we have to verify if that **vertex** exists. After that make sure that **edge **that we are trying to add** **does not already exist. If all checks pass, then we can add the **edge** to a **vertex**. (*We could use **Set** instead of **array**, but that is too much of *** ES6**).

# 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 []

So far, this is what you need to create a **Graph**. But, 99% of the time you will be asked to implement two more methods. Let’s get those aside too. We will be adding **Breadth First Search** and **Depth First Search** methods.

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

- BFS gets a starting node as an argument. (e.g
`'A'`

) - 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

Inside the **loop**:

- take an element from the
`q`

and store it in a variable. (`let current = q.pop()`

) - 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:

- Accept a starting point as an argument
`dfs(startingNode)`

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

It will be very hard for me to illustrate recursion here, but examine the `for loop`

to understand what is happening. Here is a code snippet.

Let’s go an extra mile and implement a method that checks if there is a path between two **vertices.**

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