Dan D Kim

Let's share stories

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

2022-05-12 Dan D. Kimjavascript

TLDR - jump to the code

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.

meme about how you should use another language for bfs

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)
    const neighbors = adjacencyList.has(node) ? adjacencyList.get(node) : []

    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)
    const neighbors = adjacencyList.has(node) ? adjacencyList.get(node) : []

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

That’s all. Hope this helps!