How to write a bfs without Array.shift() in Javascript

2022-05-12 Dan D. Kim

Do you do coding interviews with Javascript?

Then you may have come across this question: How can we write breadth-first search in Javascript without the `Array.shift()` function?

Why do we care? Because `Array.shift()` takes `O(N)` time.

Generic BFS logic

Here is the generic logic for BFS, from Wikipedia:

`````` 1  procedure BFS(G, root) is
2      let Q be a queue
3      label root as explored
4      Q.enqueue(root)
5      while Q is not empty do
6          v := Q.dequeue()
7          if v is the goal then
8              return v
9          for all edges from v to w in G.adjacentEdges(v) do
10              if w is not labeled as explored then
11                  label w as explored
12                  Q.enqueue(w)``````

Problem with Javascript BFS with `Array.shift()`

Here’s the problem doing it with Javascript

``````function bfs(root, adjacencyList) {
if (!root) return

const queue = [root]
const visited = new Set()

while (queue.size) {
const node = queue.shift() // <--- takes O(N) time!! So the entire BFS takes O(N^2)

for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
queue.push(neighbor)
}
}
}
}``````

How to write BFS in JS without `Array.shift()`

Use a Set.

Why? A `Set` keeps the insertion ordering. It’s pretty much a queue.

⚠ Limitation this only works with primitive values and object references, due to Set’s equality comparator. Hopefully things change with the Record/Tuple proposal

Here’s our BFS:

``````function bfs(root, adjacencyList) {
if (!root) return

const queue = new Set([root])
const visited = new Set()

while (queue.size) {
let currentNode    for (const node of queue) {      currentNode = node      break    }    queue.delete(node)