Good morning! Here's our prompt for today.

Since a graph is one of the more difficult data structures to conceptualize in a programmatic 2D manner, let's go ahead and implement it! We'll go with an adjacency list version. Note that there's also the adjacency matrix method which we will cover later.

Recall that an adjacency list is a concept in graph theory, used to describe a representation of a graph via its nodes' adjacent (neighboring) nodes. You can think of it as each vertex maintaining a list of other vertices it's connected to. Using an unordered list data structure, each list is comprised of the node's neighbors.

Here's a skeleton of the implementation. Can you fill the rest in? What could be a good data structure to model this?

1class Graph {
2  constructor(verticesCount) {
3    this.adjacencyList = {};
4  }
5
6  addVertex(nodeVal) {}
7
8  addEdge(src, dest) {}
9
10  removeVertex(nodeVal) {}
11
12  removeEdge(src, dest) {}
13}

Constraints

• Number of nodes in the graph <= 100000
• It's advised to use a HashMap for the adjacency list
• Expected time complexity for all the utility functions is O(1)
• Expected space complexity is O(n)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

    "Removing `A` should return [ 'B: C', 'C: B D E', 'D: C E G', 'E: D F C', 'F: E', 'G: D' ]"

var assert = require('assert');

​

class Graph {

  constructor() {

    // fill in this method

  }

​

  addVertex(nodeVal) {

    // fill in this method

  }

​

  addEdge(src, dest) {

    // fill in this method

  }

​

  removeVertex(val) {

    // fill in this method

  }

​

  removeEdge(src, dest) {

    // fill in this method

  }

​

  printNeighbors() {

    const result = [];

​

    for (let vertex of this.adjacencyList.keys()) {

      const neighbors = [];

​

Here's our guided, illustrated walk-through.

How do I use this guide?