Breadth-first search (BFS) is an algorithm for searching a Tree [or Graph] Data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a Queue, is needed to keep track of the child nodes that were encountered but not yet explored.

Algorithm

Breadth-first search follows Level-order tree traversal.

procedure breadthFirstSearch(graph, rootNode)
  define a Queue: queue
  define a Set: visited

  visited.add(rootNode)
  queue.enqueue(rootNode)

  while not queue.empty() do
    node = queue.dequeue()
    if node not in visited do
      visited.add(node)
      for connectedNode in graph.connectedNodes(node) do
        queue.enqueue(connectedNode)

Based on the algorithm in (“Breadth-First Search” 2022).

Complexity

Worst-case
Time\(O(\href{/posts/cardinality}{\vert V \vert} + \href{/posts/cardinality}{\vert E \vert})\)
Space\(O(\href{/posts/cardinality}{\vert V \vert})\)

Bibliography

“Breadth-First Search.” 2022. Wikipedia, June. https://en.wikipedia.org/w/index.php?title=Breadth-first_search&oldid=1091199031.