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

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.

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

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);
    });
  }
}
Prev
Breadth-First Search
Next
Pilot a Rocket
Loading...

Table of Contents