One Pager Cheat Sheet
- We can effectively implement a graph data structure by using an
adjacency list
in aHashMap
to store connected nodes, with an expected time and space complexity ofO(1)
andO(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 ahash table
, which maps each vertex to its adjacent vertices. - We can edit the adjacency lists to
add
andremove
nodes from thegraph
. - 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
, wesplice
them out of each others' lists. - We have successfully created a
graph
class usingvarious 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
104
}
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);
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
You're doing a wonderful job. Keep going!
If you had any problems with this tutorial, check out the main forum thread here.