One Pager Cheat Sheet

• We can effectively implement a graph data structure by using an adjacency list in a HashMap to store connected nodes, with an expected time and space complexity of O(1) and O(n), respectively.
• A Hash Table is an efficient data structure used to quickly lookup key-value pairs in a Graph class.
• We can store a graph representations in a hash table, which maps each vertex to its adjacent vertices.
• We can edit the adjacency lists to add and remove nodes from the graph.
• Hash Tables provide an O(1) time complexity for adding, deleting and referencing any data type in a graph, making them ideal for representing sparse graphs.
• We can simply add or remove a key from a hash table to add or remove a vertex, but removal requires us to update the adjacency list of neighboring nodes.
• An adjacency list allows for O(1) random access to a node's neighbors, allowing us to efficiently access and modify the graph with an array representation.
• We can create edges between two nodes by simply adding them to each others' adjacency lists.
• To remove an edge, we splice them out of each others' lists.
• We have successfully created a graph class using various methods.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

class Graph {

  constructor() {

    this.adjacencyList = new Map();

  }

​

  addVertex(nodeVal) {

    this.adjacencyList.set(nodeVal, []);

  }

​

  addEdge(src, dest) {

    this.adjacencyList.get(src).push(dest);

    this.adjacencyList.get(dest).push(src);

  }

​

  removeVertex(val) {

    if (this.adjacencyList.get(val)) {

      this.adjacencyList.delete(val);

    }

​

    this.adjacencyList.forEach((vertex) => {

      const neighborIdx = vertex.indexOf(val);

      if (neighborIdx >= 0) {

        vertex.splice(neighborIdx, 1);

      }

    });

  }

​

  removeEdge(src, dest) {

    const srcDestIdx = this.adjacencyList.get(src).indexOf(dest);

    this.adjacencyList.get(src).splice(srcDestIdx, 1);

Got more time? Let's keep going.

If you had any problems with this tutorial, check out the main forum thread here.