Implement a Graph Coding Interview Question | Skilled.dev
Interview Question

# Implement a Graph

## Course launching November 17, 2020

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.undirected = undirected;
}

}

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

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

``````addVertex(vertex)  {
}
``````

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

if (this.undirected) {
}
}
``````

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

});
}
``````

## 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.undirected = undirected;
}

}

if (this.undirected) {
}
}

removeVertex(vertex) {