BreadthFirstSearch.js

import Queue from '../Data-Structures/Queue/Queue'

/**
 * Breadth-first search is an algorithm for traversing a graph.
 *
 * It discovers all nodes reachable from the starting position by exploring all of the neighbor nodes at the present
 * depth prior to moving on to the nodes at the next depth level.
 *
 * (description adapted from https://en.wikipedia.org/wiki/Breadth-first_search)
 * @see https://www.koderdojo.com/blog/breadth-first-search-and-shortest-path-in-csharp-and-net-core
 */
export function breadthFirstSearch (graph, startingNode) {
  // visited keeps track of all nodes visited
  const visited = new Set()

  // queue contains the nodes to be explored in the future
  const queue = new Queue()
  queue.enqueue(startingNode)

  while (!queue.isEmpty()) {
    // start with the queue's first node
    const node = queue.dequeue()

    if (!visited.has(node)) {
      // mark the node as visited
      visited.add(node)
      const neighbors = graph[node]

      // put all its neighbors into the queue
      for (let i = 0; i < neighbors.length; i++) {
        queue.enqueue(neighbors[i])
      }
    }
  }

  return visited
}