Editing Breadth-first search (section)

== Pseudocode ==

'''Input''': A graph {{mvar|G}} and a starting vertex {{mvar|root}} of {{mvar|G}}

'''Output''': Goal state. The ''parent'' links trace the shortest path back to {{mvar|root}}<ref>{{Cite book|last=Cormen, Thomas H.|url=http://worldcat.org/oclc/1006880283|title=Introduction to algorithms|isbn=978-81-203-4007-7|chapter=22.2 Breadth-first search|date=January 2010 |publisher=Prentice-Hall Of India Pvt. Limited |oclc=1006880283}}</ref>

  1  '''procedure''' BFS(''G'', ''root'') '''is'''
  2      let ''Q'' be a queue
  3      label ''root'' as explored
  4      ''Q''.enqueue(''root'')
  5      '''while''' ''Q'' is not empty '''do'''
  6          ''v'' := ''Q''.dequeue()
  7          '''if''' ''v'' is the goal '''then'''
  8              '''return''' ''v''
  9          '''for all''' edges from ''v'' to ''w'' '''in''' ''G''.adjacentEdges(''v'') '''do'''
 10              '''if''' ''w'' is not labeled as explored '''then'''
 11                  label ''w'' as explored
 12                  ''w''.parent := ''v''
 13                  ''Q''.enqueue(''w'')

=== More details ===

This non-recursive implementation is similar to the non-recursive implementation of [[depth-first search]], but differs from it in two ways:

# it uses a [[Queue (abstract data type)|queue]] ([[First In First Out]]) instead of a [[Stack (abstract data type)|stack]] (Last In First Out) and
# it checks whether a vertex has been explored before enqueueing the vertex rather than delaying this check until the vertex is dequeued from the queue.
If {{mvar|G}} is a [[Tree (data structure)|tree]], replacing the queue of this breadth-first search algorithm with a stack will yield a depth-first search algorithm. For general graphs, replacing the stack of the iterative depth-first search implementation with a queue would also produce a breadth-first search algorithm, although a somewhat nonstandard one.<ref>{{Cite web|title=Stack-based graph traversal ≠ depth first search|url=https://11011110.github.io/blog/2013/12/17/stack-based-graph-traversal.html|access-date=2020-06-10|website=11011110.github.io}}</ref>

The ''Q'' queue contains the frontier along which the algorithm is currently searching.

Nodes can be labelled as explored by storing them in a set, or by an attribute on each node, depending on the implementation.

Note that the word ''node'' is usually interchangeable with the word ''vertex''.

The ''parent'' attribute of each node is useful for accessing the nodes in a shortest path, for example by backtracking from the destination node up to the starting node, once the BFS has been run, and the predecessors nodes have been set.

Breadth-first search produces a so-called ''breadth first tree''. You can see how a ''breadth first tree'' looks in the following example.

=== Example ===

The following is an example of the breadth-first tree obtained by running a BFS on [[Germany|German]] cities starting from ''Frankfurt'':

[[Image:MapGermanyGraph.svg|thumb|250px|center|An example map of [[Southern Germany]] with some connections between cities]]

[[Image:GermanyBFS.svg|thumb|250px|center |The breadth-first tree obtained when running BFS on the given map and starting in [[Frankfurt]]]]