How to determine if there exists a route between two nodes in JavaScript

Here’s one means of determining whether there exists a route between two nodes in JavaScript.
Another acceptable solution would involve depth-first search.

routeBetweenNodesTry in REPL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// BFS
function search(graph, start, end) {
if (start === end) return true;
// functions like a queue
const queue = [];
for (const node of graph.getNodes()) {
node.state = 'unvisited';
}
start.state = 'visiting';
queue.push(start);
let node;
while (queue.length) {
node = queue.shift(); // dequeue
if (node) {
for (const neighbor of graph.getAdjacentNeighbors(node)) {
if (neighbor.state === 'unvisited') {
if (neighbor === end) {
return true;
} else {
neighbor.state = 'visiting';
queue.push(neighbor); // enqueue
}
}
}
node.state = 'visited';
}
}
return false;
}
// Adjacency list representation of a graph
function Graph(iterable) {
this.list = new Map(iterable); // [[key, value], [key, value]]
}
Graph.prototype.addVertex = function(vertex) {
!this.list.get(vertex) && this.list.set(vertex, []); // prevents overwriting a vertex
}
Graph.prototype.addEdge = function(from, to) {
this.list.get(from).push(to) // does not account for edge case where we try to add edge again
this.list.get(to).push(from);
}
Graph.prototype.getNodes = function() {
return Array.from(this.list.keys());
};
Graph.prototype.getAdjacentNeighbors = function(target) {
return this.list.get(target) || [];
}

Tests can be found at REPL.it