Breadth First Search (BFS) Algorithm and Example Demonstration

Breadth First Search (BFS) algorithm and example demonstration.

In computer science, Breadth-First Search (BFS) is an algorithm that traverses or searches trees or graphs.

It starts at the root node, explores all the adjacent nodes, and then goes down layer by layer until it finds the target node or traverses the entire graph.

BFS is often used to find the shortest path problem, such as the shortest path in a maze, the shortest relationship chain in a social network, etc.

This article will use queues to implement BFS through an example of a maze problem and show how to find the shortest path from the starting point to the ending point.

\n#

Labyrinth problem description.

Suppose we have a 2D maze of m x n, where some locations are obstacles (denoted by 1) and others are passable (denoted by 0).

Our goal is to find the shortest path from the starting point (usually the upper left corner) to the end point (usually the lower right corner).

If no such path exists, the return fails.

\n#

BFS algorithm steps.

1. # Initialization #: Create a queue to store the nodes of the current layer and their path information, and add the starting point to the queue.

At the same time, create a collection to record the nodes that have been visited to avoid repeated visits.

2. # Circular processing #: When the queue is not empty, take out the node at the head of the queue and check whether the node is the target node.

If yes, output the path and end.

Otherwise, add its neighbor nodes in four directions to the queue (if they have not been accessed and are not obstacles).

3. # mark access #: mark the current node as accessed to prevent repeated access.

4. # Update path #: For each new neighbor node added to the queue, update its path information, that is, add the current node on the basis of its predecessor node.

5. # Continue to search #: Repeat steps 2-4 until the target node is found or the queue is empty.

\n#

Code implementation.

The following is a code example of using Python to implement the above BFS algorithm:

from collections import deque

def bfs_maze(maze):
    # 定义方向向量，上、下、左、右
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # 获取迷宫的维度
    m, n = len(maze), len(maze[0])
    
    # 定义起点和终点
    start = (0, 0)
    end = (m-1, n-1)
    
    # 初始化队列和已访问集合
    queue = deque([(start, [start])])  # 队列中存储元组，第一个元素是节点坐标，第二个元素是路径
    visited = set()
    visited.add(start)
    
    while queue:
        # 取出队列头部的节点和路径
        current, path = queue.popleft()
        
        # 检查是否到达终点
        if current == end:
            return path  # 返回路径
        
        # 遍历四个方向
        for direction in directions:
            new_x, new_y = current[0] + direction[0], current[1] + direction[1]
            if 0 <= new_x < m and 0 <= new_y < n and not visited.get((new_x, new_y), False):
                if maze[new_x][new_y] == 0:  # 确保不是障碍物
                    visited.add((new_x, new_y))
                    queue.append(((new_x, new_y), path + [(new_x, new_y)]))
    
    return None  # 如果没有找到路径，返回None

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

# 调用函数并打印结果
path = bfs_maze(maze)
print("Shortest path from start to end:", path)

\n#

Code explanation.

1. # direction vector #: directionsFour possible movement directions (up, down, left, right) are defined.

2. # start and end #: startSumendRepresents the starting and ending coordinates of the maze, respectively.

3. # Queue and Visited Collection #: queueIt is a double-ended queue, which is used to store the nodes and their path information of the current layer; visitedIs a collection that records the nodes that have been visited.

4. # Loop processing #: use while queueThe nodes in the queue are processed in a loop until the target node is found or the queue is empty.

5. # Neighbor node check #: For each current node, check whether the neighbor nodes in the four directions are accessible (not accessed and not an obstacle), and then add the accessible neighbor nodes to the queue.

6. # Path Update #: For each new neighbor node added to the queue, update its path information.

7. # Return result #: If the target node is found, the path is returned; otherwise, the path is returned None。

\n#

Summarize.

Breadth First Search (BFS) is an effective graph traversal algorithm, especially suitable for finding the shortest path problem.

By using queues to manage pending nodes, BFS can systematically explore each layer of nodes in the graph until it finds the target node or traverses the entire graph.

In the maze problem, BFS can help us find the shortest path from the starting point to the ending point, thereby solving the navigation and path planning problems in practical application scenarios.

I hope this article can help you understand the principle and application of the BFS algorithm, and deepen your impression through example demonstrations.