Breadth-First Search | Skilled.dev
Learn

Breadth-First Search

Course launching November 17, 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓
Loading...
Credit: VisuAlgo
Pros 🔥
  • Find the shortest path
    It considers all the nodes closest first
Cons 🤕
  • More memory
    BFS typically requires more memory (commonly assumed)

Breadth-first search (BFS) traverses by checking the nodes closest to a parent before moving on. BFS is used when we want to find the shortest path or closest neighbors.

BFS is implemented using a queue data structure. Because we access the items in FIFO order, we visit all the edges of a given node first and then progress onward.

BFS can be seen commonly in the real-world. For example, on Facebook we are recommended friends. What they do is create a graph of all the users and recommend the people closest to your friends since you are also more likely to be friends with them. The same thought process happens when Netflix recommends shows or Amazon recommends products - the closer the match is to you based on similar people, the more likely it's a fit.

To implement BFS, we will use a graph node that stores data and its edges. The edges variable is just an array of pointers to its sibling nodes. We will also assume our graph is undirected.

Nodes will take the following form:

class GraphNode {
  constructor(data) {
    this.data = data;
    this.edges = [];
  }
}

We perform BFS iteratively by using a queue data structure.

const breadthFirstSearch = (startingNode) => {
  const bfsQueue = [startingNode];
  const visitedNodes = new Set();

  visitedNodes.add(startingNode);

  while(bfsQueue.length > 0) {
    const node = bfsQueue.pop();

    // Use node value for the question
    visit(node);

    node.edges.forEach(childNode => {
      if (!visitedNodes.has(childNode)) {
        bfsQueue.unshift(childNode);
        visitedNodes.add(childNode);
      }
    });
  }
}
Prev
Depth-First Search
Next
Implement a Graph
Loading...

Table of Contents