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
- We initially create a root node with an initial state, and add it to a queue and tree.
- 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.
- This process is repeated until we either find the goal state or have exhausted all of the nodes in our search tree.
- Since our connection data is in a graph structure, we have to check whether each node has been visited before.
- So, we add...