Theory

Breadth-First Search (BFS) explores the search space level by level, moving to the next level only when all states at the current level have been explored. We implement BFS using two lists: open and closed. The open list stores generated states whose children have not been examined, while the closed list records states that have been explored. States are added to the open list in the order they are generated and are removed using a first-in-first-out (FIFO) queue structure. The objective is to find routes using BFS with open and closed lists based on user-provided input.

Breadth-First Search (BFS) with open and closed lists

1. Initialization:
• start at the initial state.
• Initialize an empty open list and closed list.
2. Add Initial State:
• Add the initial state to the open list.
3. Explore States:
• While the open list is not empty:
• Remove the first state from the open list (using a FIFO queue).
• Add this state to the closed list to mark it as explored.
• Generate all possible successor states from the current state.
• For each successor state:
• If it has not already been explored (not in the closed list):
• Add it to the open list.
• Mark it as a child of the current state.
4. Termination:
• Repeat the process until either the goal state is found or the open list becomes empty.