farazamiruddin

Friday, October 22 2021

Breadth First Search in JavaScript

Breadth first search is a search algorithm used for searching graphs. It will search all of the closest nodes, then the following closest nodes. The data structure used to implement this algorithm is a queue. Recall, queues use a first-in-first out principle, which is how we will traverse each of the closest nodes first.

For the sake of this example, this is the interface of a node.

interface Node {
  key: string;
  value: any;
  children: Node[] | null;
}

To start, we can write our function signature.

function breadthFirstSearch(start, visitFn) {}

We take in two params;

  • start - the node where we want to start our search from.
  • visitFn - a callback that is called every time we visit a node.

First, we will implement our queue. We can use an array in javascript as a queue. The queue should start off with the start node, so that we have a starting point.

We will also keep track of the nodes we have visited with an visited map. We need to do this because some edges may point to a node we already visited, and we only want to visit a node once.

function breadthFirstSearch(start, visitFn) {
  let queue = [start];
  let visited = {};
}

To start our search, we will use a while loop. We want to search through all the nodes until the queue is empty. When the queue is empty, we know we have visited every node.

function breadthFirstSearch(start, visitFn) {
  let queue = [start];
  let visited = {};

  while (queue.length) {}
}

In our loop, we dequeue the first node out of the queue. Recall, queues are first-in-first-out, so the first node we added to the queue will be pulled out. We can use the .shift() method on our array implementation of a queue to get the node at index 0.

function breadthFirstSearch(start, visitFn) {
  let queue = [start];
  let visited = {};

  while (queue.length) {
    const current = queue.shift();
  }
}

Next, we check if we have already have visited this node. If we have, we can move on to the next iteration by using continue.

function breadthFirstSearch(start, visitFn) {
  let queue = [start];
  let visited = {};

  while (queue.length) {
    const current = queue.shift();
    if (visited[current.key]) continue;
  }
}

If we haven’t visited the node, then we need to visit it! We call the visitFn with the node, and add the node’s key to the visited map.

function breadthFirstSearch(start, visitFn) {
  let queue = [start];
  let visited = {};

  while (queue.length) {
    const current = queue.shift();
    if (visited[current.key]) continue;

    visitFn(current);
    visited[current.key] = true;
  }
}

Before finishing this iteration, we need to see if the current node has any children. If it does, we will add each child to the queue. To accomplish this, we can use a for loop to add each child to the queue.

function breadthFirstSearch(start, visitFn) {
  let queue = [start];
  let visited = {};

  while (queue.length) {
    const current = queue.shift();
    if (visited[current.key]) continue;

    visitFn(current);
    visited[current.key] = true;

    for (let child of current.children) {
      queue.push(child);
    }
  }
}

Great, we have implemented a breadth first search in JavaScript. Here is the final result with annotations.

/**
 * start   - Node where we start our search from.
 * visitFn - A callback called with each Node we visit.
 */
function breadthFirstSearch(start, visitFn) {
  // Create a queue, and add the first (start) node to it as a starting point.
  let queue = [start];
  // Create a map of nodes we have visited, so that we don't visit a node twice.
  let visited = {};

  // While the queue isn't empty...
  while (queue.length) {
    // Get the current node by shifting the node at 0 off the array.
    const current = queue.shift();
    // Check if we have already visited this node. If we have, skip this loop.
    if (visited[current.key]) continue;

    // If we get here, we haven't visited this node. Visit it!
    visitFn(current);
    // Add it's key to the visited map so we don't visit it again.
    visited[current.key] = true;

    // Add any of the current node's children to our queue to visit later.
    for (let child of current.children) {
      queue.push(child);
    }
  }
}