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

Implement a Graph

Course launching August 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.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓

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 add 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(data)  {
    // Add a node to the adjacency list
  }

  addEdge(source, destination) {
    // Connect two nodes by an edge
    // If undirected, create a reciprocal edge
  }

  removeVertex(data) {
    // Remove a data and clean up the edges pointing to it
  }
}

The graph nodes will take the following form:

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

Technically an adjacency list just uses the node data, where the hash table key is the current node and the value is an array of its connected nodes. To provide more clarity, we're going to actually store a graph node in our hash table and access its connected node through the edges property which is also an array of strings. The concept is almost identical, but the implementation is just slightly different.

Add a Vertex

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

addVertex(data)  {
  this.adjacencyList[data] = new GraphNode(data);
}

Add an Edge

Adding an edge is how 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].edges.push(destination);

  if (this.undirected) {
    this.adjacencyList[destination].edges.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(data) {
  delete this.adjacencyList[data];

  Object.values(this.adjacencyList).forEach(vertex => {
    vertex.edges = vertex.edges.filter(e => e !== data);
  });
}

Solution

With that, that 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(data)  {
    this.adjacencyList[data] = new GraphNode(data);
  }

  addEdge(source, destination) {
    this.adjacencyList[source].edges.push(destination);

    if (this.undirected) {
      this.adjacencyList[destination].edges.push(source);
    }
  }

  removeVertex(data) {
    delete this.adjacencyList[data];

    Object.values(this.adjacencyList).forEach(vertex => {
      vertex.edges = vertex.edges.filter(e => e !== data);
    });
  }
}
Prev
Breadth-First Search
Next
Pilot a Rocket

Table of Contents