Breadth-first Search - Algorithm

Algorithm

Graph and tree
search algorithms
  • α — β
  • A*
  • B*
  • Beam
  • Bellman–Ford
  • Best-first
  • Bidirectional
  • Borůvka
  • Branch & bound
  • BFS
  • British Museum
  • D*
  • DFS
  • Depth-limited
  • Dijkstra
  • Edmonds
  • Floyd-Warshall
  • Hill climbing
  • Iterative deepening
  • Kruskal
  • Johnson
  • Lexicographic BFS
  • Prim
  • Uniform-cost
Listings
  • Graph algorithms
  • Search algorithms
  • List of graph algorithms
Related topics
  • Dynamic programming
  • Graph traversal
  • Tree traversal
  • Search games

The algorithm uses a queue data structure to store intermediate results as it traverses the graph, as follows:

  1. Enqueue the root node
  2. Dequeue a node and examine it
    • If the element sought is found in this node, quit the search and return a result.
    • Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.
  3. If the queue is empty, every node on the graph has been examined – quit the search and return "not found".
  4. If the queue is not empty, repeat from Step 2.

Note: Using a stack instead of a queue would turn this algorithm into a depth-first search.

Read more about this topic:  Breadth-first Search