A queue is a data structure whose elements are removed in the order they were added. This first-in, first-out (FIFO) behavior works like a line of people: the earliest arrival is served first. section 2.10 section 2.9
Queues are especially useful when work must be handled in arrival order. Breadth-first search (BFS) uses one to process every node at the current depth before moving to the next depth, allowing shortest paths in unweighted graphs to be found. section 2.9
A BFS queue follows this sequence:
- Enqueue the root node and mark it as visited. section 2.10
- Dequeue the next node and inspect its neighbors. section 2.10
- For each unvisited neighbor, record its parent, mark it visited, and enqueue it for later processing. section 2.10
- Continue until the goal is found or the queue becomes empty. section 2.10
Exploring a maze
Starting at the player's position, BFS places the root location in the queue. It removes that location, adds each possible north, south, east, or west neighbor, and then processes those neighbors in order. Because each level is completed before the next, the first discovered goal follows a shortest path when every move has equal cost. section 2.10 section 2.9
def run_bfs(maze_puzzle, current_point, visited_points):
queue = deque()
queue.append(current_point)
visited_points.append(current_point)
while queue: #A
current_point = queue.popleft()
neighbors =
➥maze_puzzle.get_neighbors(current_point) #B
for neighbor in neighbors: #C
if not is_in_visited_points(neighbor,
➥visited_points): #D
neighbor.set_parent(current_point) #D
queue.append(neighbor) #D
visited_points.append(neighbor) #D
if maze_puzzle
➥.get_current_point_value(neighbor)
➥=='*': #E
return neighbor #E
return 'No path to the goal found.' #F
A Python-style implementation shows a deque, append for enqueueing, and popleft for dequeueing while tracking visited points and parent links. section 2.10
