# Implement a Graph

## Course launching November 17, 2020

**Follow me on YouTube** for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

We will implement a graph using an . We will assume the data for vertexes (nodes) can't be duplicated, and this value will represent the key in the adjacency list as well.

```
{
'a': ['b', 'c', 'd'],
'b': ['a', 'd'],
'c': ['a'],
'd': ['a', 'b', 'e'],
'e': ['d']
}
```

When we initialize our graph, we will allow the user to pass a boolean value to indiciate if it is undirected. This value will default to true.

We will implement methods to create vertexes, add edges to connect them, and remove a vertex. The implementation will take the following shape:

```
class Graph {
constructor(undirected = true) {
this.adjacencyList = {};
this.undirected = undirected;
}
addVertex(vertex) {
// Add a node to the adjacency list
}
addEdge(source, destination) {
// Connect two nodes by an edge
// If undirected, create a reciprocal edge
}
removeVertex(vertex) {
// Remove a vertex and clean up the edges pointing to it
}
}
```

### Note: Graph as Nodes

```
class GraphNode {
constructor(data) {
this.data = data;
this.edges = [];
}
}
```

Another common way to work with graphs is directly through nodes. You'll gain a deep understanding of how to do this as you work through this module, so we are looking at another implementation in this lesson.

## Add a Vertex

This method will add a node to the adjency matrix. Initially, this node is not connected to any other items.

```
addVertex(vertex) {
this.adjacencyList[vertex] = [];
}
```

## Add an Edge

Adding an edge is how we indicate nodes are connected. If our graph is undirected, we also need to add a reciprocal edge pointing back.

```
addEdge(source, destination) {
this.adjacencyList[source].push(destination);
if (this.undirected) {
this.adjacencyList[destination].push(source);
}
}
```

## Remove a Vertex

To delete a vertex, we remove it from the adjacency list. We also must delete all the edges that point to it.

```
removeVertex(vertex) {
delete this.adjacencyList[vertex];
Object.keys(this.adjacencyList).forEach(node => {
this.adjacencyList[node] = this.adjacencyList[node].filter(v => v !== vertex);
});
}
```

## Solution

With that, we have a complete graph implementation that is clean and simple. You can explore it further and run code in the REPL.

```
class Graph {
constructor(undirected = true) {
this.adjacencyList = {};
this.undirected = undirected;
}
addVertex(vertex) {
this.adjacencyList[vertex] = [];
}
addEdge(source, destination) {
this.adjacencyList[source].push(destination);
if (this.undirected) {
this.adjacencyList[destination].push(source);
}
}
removeVertex(vertex) {
delete this.adjacencyList[vertex];
Object.keys(this.adjacencyList).forEach(node => {
this.adjacencyList[node] = this.adjacencyList[node].filter(v => v !== vertex);
});
}
}
```

Table of Contents