The BFS algorithm

In this section, we'll look at the flow of the BFS algorithm, how a queue is used, and how graph data affects the algorithm. The flow of the BFS algorithm is similar to that of DFS, but instead of using a stack data structure, a queue data structure is used.

A flowchart of the BFS algorithm can be illustrated as follows:

Figure 13
  1. We initially create a root node with an initial state, and add it to a queue and tree.
  2. A node is dequeued from the queue, and we check whether it has the goal state. If it does, we end our search. If it doesn't, we find the child nodes of the dequeued node and add them to the queue entry.
  3. This ...

Get Hands-On Artificial Intelligence for Search now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.