Learning JavaScript Data Structures and Algorithms - Third Edition

Breadth-first search (BFS)

The BFS algorithm starts traversing the graph from the first specified vertex and visits all its neighbors (adjacent vertices) first, one layer of the graph at a time. In other words, it visits the vertices first widely and then deeply, as demonstrated by the following diagram:

These are the steps followed by the BFS algorithm, starting at vertex v:

1. Create a queue Q
2. Mark v as discovered (grey) and enqueue v into Q
3. While Q is not empty, perform the following steps:
   1. dequeue u from Q
   2. Mark u as discovered (grey)
   3. enqueue all the unvisited (white) neighbors w of u
   4. Mark u as explored (black)

The BFS algorithm is declared ...