Breadth-First Search |

Breadth-First Search

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) { = data;
    this.edges = [];

We perform BFS iteratively by using a queue data structure. The full code can be found in this REPL.

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


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

    // Use node value for the question

    node.edges.forEach(childNode => {
      if (!visitedNodes.has(childNode)) {

Table of Contents