Breadth First Search (BFS) Algorithm and Example Demonstration

The maze problem is a classic problem that requires us to find the shortest path from the starting point to the ending point in a maze of walls and doors. In this problem, we usually use the breadth-first search (BFS) algorithm to solve this problem. BFS is an algorithm used to traverse or search trees or graphs. In the maze problem, we can think of the maze as a graph in which each position is a node, and each node has a list of adjacent nodes. By using queues to implement BFS, we can access the next adjacent node in each iteration until the end point is found. When implementing this solution, we need to first create a queue and add the starting point to the queue. Then, we start the iteration, and in each iteration, we take a node from the queue and add all its adjacent nodes that have not been accessed to the queue. In this way, we can ensure that we always follow the shortest path. Finally, we add the endpoint to the queue and continue to iterate until the queue is empty. At this point, we have found the shortest path from the start to the end.

Breadth First Search (BFS) is a very effective algorithm when solving maze problems.

It finds the shortest path from the starting point to the ending point by expanding the nodes layer by layer.

This article will detail how to use queues to implement BFS, combined with code examples to help you understand this process.

What is Breadth First Search (BFS)?.

Breadth-first search is a graph traversal algorithm that starts from a starting node, first accesses all adjacent nodes, and then accesses the neighbor nodes of these adjacent nodes in turn.

This process continues until the target node is found or all nodes are traversed.

BFS is characterized by a hierarchical search, so it can ensure that the path found is the shortest.

Basic steps of BFS.

1. # Initialization #: Create a queue and queue the starting node, and mark the starting node as accessed.

2. # Loop processing #: When the queue is not empty, do the following: -Take a node from the queue.

-Check whether the node is the target node, and if so, end the search.

-Otherwise, queue all unvisited neighbor nodes of this node and mark these neighbor nodes as visited.

3. # Path reconstruction #: If the target node is found, the path can be rebuilt by recording the predecessor node of each node.

Use queues to implement BFS.

To understand BFS more intuitively, let's look at a specific code example.

Suppose we have a two-dimensional maze in which 0Indicates the path that can be taken, 1Indicates an obstacle.

We need to find from the starting point (0, 0)To the end (n-1, m-1)The shortest path.


from collections import deque

def bfs_maze(maze):
    # 获取迷宫的尺寸
    rows, cols = len(maze), len(maze[0])
    
    # 定义四个方向的移动向量
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # 初始化队列和访问标记
    queue = deque([(0, 0)])
    visited = set((0, 0))
    
    # 用于记录路径
    parent = {(0, 0): None}
    
    while queue:
        x, y = queue.popleft()
        
        # 如果到达终点，重建路径
        if (x, y) == (rows - 1, cols - 1):
            path = []
            while (x, y) is not None:
                path.append((x, y))
                x, y = parent[(x, y)]
            return path[::-1]
        
        # 遍历四个方向
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            
            # 检查新位置是否在迷宫范围内且未被访问过
            if 0 <= nx < rows and 0 <= ny < cols and maze[nx][ny] == 0 and (nx, ny) not in visited:
                queue.append((nx, ny))
                visited.add((nx, ny))
                parent[(nx, ny)] = (x, y)
    
    # 如果没有找到路径，返回空列表
    return []

# 示例迷宫
maze = [
    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]

# 调用BFS函数并打印结果
shortest_path = bfs_maze(maze)
print("Shortest Path:", shortest_path)

Code explanation.

1. # Initialization part #: \n -rowsSumcolsStore the number of rows and columns of the maze respectively.

\n -directionsIs a list of four directional movement vectors for conveniently calculating the positions of adjacent nodes.

\n -queueIs a double-ended queue for storing nodes to be processed.

Will start at the beginning (0, 0)Join the team.

\n -visitedIs a collection used to record nodes that have been visited to avoid repeated visits.

\n -parentIs a dictionary that records the precursor nodes of each node for subsequent reconstruction paths.

2. # main loop #: -Take one node from the queue at a time (x, y)。

-If the current node is the end (rows - 1, cols - 1), then through parentThe dictionary rebuilds the path and returns.

-Otherwise, traverse the four directions and calculate the new position (nx, ny)。

If the new location is within the maze and has not been accessed, it is queued and marked as accessed, while its predecessor node is recorded.

3. # path reconstruction #: -If the end is found, pass parentThe dictionary goes back from the end to the beginning, constructing a complete path.

-If the queue is empty and the end point is not found, an empty list is returned, indicating that there is no viable path.

Considerations in practical applications.

In practical applications, BFS is not only suitable for simple maze problems, but also for other scenarios that require the shortest path, such as: - # Network Routing #: Find the shortest path for packet transmission.

- # Robot Navigation #: Plan the shortest path of the robot from the starting point to the ending point.

- # Game Development #: Path planning for AI characters.

By understanding and mastering the BFS algorithm, you can effectively solve many practical problems and improve the efficiency and performance of the program.

I hope this article can help you better understand and apply the BFS algorithm.