具体来说，广度优先搜索算法使用队列来存储待遍历节点，每次从队列的头部取出一个节点进行扩展，将其未被访问的相邻节点加入队列尾部。由于该算法优先遍历距离起点较近的节点，因此能够找到最短路径。广度优先搜索算法的时间复杂度为O(V+E)，其中V为节点数，E为边数。
算法由来
广度优先搜索算法是一种常用的图形搜索算法，它是一种盲目搜索算法，没有预先知道目标位置的具体情况，只是逐步搜索，直到找到目标为止。广度优先搜索算法的由来可以追溯到19世纪初期，英国数学家查尔斯·巴贝奇（Charles Babbage）提出了一种计算机机器，被认为是计算机的鼻祖，被称为巴贝奇机（Babbage Engine）。
巴贝奇机的理念是将一系列数学运算自动化，从而实现计算机的自动化。他认为可以用机械来模拟人的思考过程。他的设想是使用可编程的机械设备来完成各种数学运算和逻辑推理，从而实现“一切可计算的事物都可以用机器来计算”。
简单的DEMO
我们可以定义了一个 bfs 函数，该函数接受三个参数：一个字典表示图的邻接表，一个起始节点和一个目标节点，函数内实现具体如下：
- 函数首先创建一个队列用于存储遍历的节点，将起始节点加入队列，并创建一个列表用于记录已经遍历过的节点。
- 然后，函数循环遍历队列，取出队首节点，进入判断。
- 如果该节点未被遍历过，则将其标记为已遍历，并将其所有相邻节点加入队列。
- 如果取出的节点是目标节点，则返回记录遍历节点的列表。
- 如果起点到终点没有可达路径，则返回空列表。
fromcollectionsimportdequedefbfs(graph, start, end): # 创建一个队列用于存储遍历的节点queue=deque() # 将起始节点加入队列queue.append(start) # 创建一个列表用于记录已经遍历过的节点visited= [] # 遍历队列，直到队列为空whilequeue: # 取出队首节点node=queue.popleft() # 如果该节点未被遍历过，则将其标记为已遍历，并将其所有相邻节点加入队列ifnodenotinvisited: visited.append(node) ifnode==end: returnvisitedqueue.extend(graph[node]) # 如果起点到终点没有可达路径，则返回空列表return [] # 测试graph= { 'A': ['B', 'C'], 'B': ['A', 'D', 'E'], 'C': ['A', 'F'], 'D': ['B'], 'E': ['B', 'F'], 'F': ['C', 'E'] } print(bfs(graph, 'A', 'F')) # 输出 ['A', 'B', 'C', 'D', 'E', 'F']
需要注意graph会组成一个有向无环图（DAG），其中每个键代表一个节点，其值为一个包含其邻居节点的列表。bfs其实就是使用该图进行广度优先搜索，查找起点A到终点F的最短路径。
注意：有同学看到这里怀疑bfs的最短应该是ACF才对，这是因为这里的算法是广度方向的遍历，而不是深度
也就是先遍历与起点相邻的节点，再遍历与这些节点相邻的节点，以此类推。在这个例子中，A节点与B和C相邻，因此A的相邻节点B和C会先加入队列中，接着队列中首先取出的节点是B，然后将B的相邻节点A、D和E加入队列中，此时队列中的节点顺序为[C, A, D, E]。接下来，队列中的节点C会被取出，C的相邻节点F也会被加入队列，此时队列中的节点顺序为[A, D, E, F]。以此类推，直到遍历到终点节点F，才会结束循环并返回遍历过的节点列表。因此，最终输出的结果是['A', 'B', 'C', 'D', 'E', 'F']，而不是['A', 'C', 'F']。
迷宫问题
配合一个比较简单的问题，广度优先搜索算法的代码复杂度会再次提升一下。
迷宫问题是指在一个迷宫中找到从起点到终点的一条路径的问题。在一个二维网格中，迷宫通常由障碍物和空格组成，其中障碍物表示不可通过的区域，空格表示可以通过的区域。要找到一条从起点到终点的路径，需要遵循以下规则：
- 只能在空格上移动，不能穿过障碍物。
- 可以向上、向下、向左或向右移动一格，但不能移动到迷宫外部。
- 起点和终点都是空格。
- 如果从起点到终点有多条路径，则需要找到其中一条最短的路径。
解决迷宫问题的常用算法是广度优先搜索算法。通过将起点加入队列，并依次遍历其相邻节点，不断扩展队列，直到找到终点或队列为空。在遍历过程中，需要记录每个节点是否被访问过，以避免重复访问和死循环。找到终点后，可以通过回溯的方式，从终点一直追溯到起点，找到一条最短路径。
fromcollectionsimportdequedefbfs(maze, start, end): # 迷宫的行数和列数rows=len(maze) cols=len(maze[0]) # 队列用于存储遍历的节点queue=deque() # 将起始节点加入队列queue.append(start) # 创建一个列表用于记录已经遍历过的节点visited=set() # 遍历队列，直到队列为空whilequeue: # 取出队首节点row, col=queue.popleft() # 如果该节点未被遍历过，则将其标记为已遍历，并将其所有相邻节点加入队列if (row, col) notinvisited: visited.add((row, col)) if (row, col) ==end: returnTrue# 将当前节点的四个相邻节点加入队列ifrow>0andmaze[row-1][col] !='X': queue.append((row-1, col)) ifrow<rows-1andmaze[row+1][col] !='X': queue.append((row+1, col)) ifcol>0andmaze[row][col-1] !='X': queue.append((row, col-1)) ifcol<cols-1andmaze[row][col+1] !='X': queue.append((row, col+1)) # 如果起点到终点没有可达路径，则返回 FalsereturnFalse# 测试maze= [ ['S', ' ', ' ', ' ', 'X', ' ', 'X', ' ', 'X'], ['X', 'X', ' ', 'X', 'X', ' ', ' ', ' ', 'X'], ['X', 'X', ' ', ' ', ' ', ' ', ' ', 'X', ' '], ['X', ' ', 'X', 'X', 'X', ' ', 'X', ' ', 'X'], [' ', ' ', ' ', ' ', ' ', ' ', ' ', 'X', 'X'], ['X', ' ', 'X', ' ', 'X', ' ', ' ', ' ', 'X'], ['X', 'X', ' ', 'X', ' ', ' ', 'X', ' ', ' '], [' ', ' ', ' ', 'X', 'X', 'X', 'X', ' ', 'X'], ['X', ' ', ' ', ' ', ' ', 'X', 'X', 'E', ' '], ] start= (0, 0) end= (8, 7) print(bfs(maze, start, end)) # 输出 True
返回最短路径的迷宫问题
如果要返回最短路径的值，而不是返回是否能够得出结果，我们就需要对代码进行微调。
具体来说，我们从起点开始，依次遍历所有可达节点，每次遍历一层。它使用一个队列来保存待遍历的节点，使用一个集合来保存已经遍历过的节点，使用一个列表来保存到达每个节点的路径。在遍历时，它从队列中取出一个节点，检查其四个相邻节点是否可达，并将它们加入队列，同时记录到达这些节点的路径。如果找到了终点，算法就返回从起点到终点的最短路径。如果遍历完所有可达节点，仍然没有找到终点，算法就返回 None。
fromcollectionsimportdequedefbfs(maze, start, end): # 迷宫的行数和列数rows=len(maze) cols=len(maze[0]) # 队列用于存储遍历的节点及其路径queue=deque() # 将起始节点及其路径加入队列queue.append((start, [start])) # 创建一个列表用于记录已经遍历过的节点visited=set() # 遍历队列，直到队列为空whilequeue: # 取出队首节点及其路径 (row, col), path=queue.popleft() # 如果该节点未被遍历过，则将其标记为已遍历，并将其所有相邻节点及其路径加入队列if (row, col) notinvisited: visited.add((row, col)) if (row, col) ==end: returnpath# 将当前节点的四个相邻节点及其路径加入队列ifrow>0andmaze[row-1][col] !='X': queue.append(((row-1, col), path+ [(row-1, col)])) ifrow<rows-1andmaze[row+1][col] !='X': queue.append(((row+1, col), path+ [(row+1, col)])) ifcol>0andmaze[row][col-1] !='X': queue.append(((row, col-1), path+ [(row, col-1)])) ifcol<cols-1andmaze[row][col+1] !='X': queue.append(((row, col+1), path+ [(row, col+1)])) # 如果起点到终点没有可达路径，则返回 NonereturnNone# 测试maze= [ ['S', ' ', ' ', ' ', 'X', ' ', 'X', ' ', 'X'], ['X', 'X', ' ', 'X', 'X', ' ', ' ', ' ', 'X'], ['X', 'X', ' ', ' ', ' ', ' ', ' ', 'X', ' '], ['X', ' ', 'X', 'X', 'X', ' ', 'X', ' ', 'X'], [' ', ' ', ' ', ' ', ' ', ' ', ' ', 'X', 'X'], ['X', ' ', 'X', ' ', 'X', ' ', ' ', ' ', 'X'], ['X', 'X', ' ', 'X', ' ', ' ', 'X', ' ', ' '], [' ', ' ', ' ', 'X', 'X', 'X', 'X', ' ', 'X'], ['X', ' ', ' ', ' ', ' ', 'X', 'X', 'E', ' '], ] start= (0, 0) end= (8, 7) shortest_path=bfs(maze, start, end) ifshortest_path: print(shortest_path) # 输出
A*算法
广度优先搜索算法的复杂度与遍历的节点数有关。在该算法中，每个节点最多只会被遍历一次，因此算法的时间复杂度为 O(V+E)，其中 V 是节点数，E 是边数。另外，算法使用了一个队列来存储待遍历的节点，队列的最大长度与图的最长路径有关，因此空间复杂度也为 O(V+E)。
A* 算法在广度优先搜索算法的基础上，引入了启发式函数来评估每个节点到目标节点的距离估计值，从而更加智能地搜索最短路径。
importheapqdefheuristic_cost_estimate(start, end): # 定义启发式函数returnabs(end[0] -start[0]) +abs(end[1] -start[1]) defa_star(maze, start, end): # 迷宫的行数和列数rows=len(maze) cols=len(maze[0]) # 将起始节点加入开放列表open_list= [(heuristic_cost_estimate(start, end), 0, start, [])] # 创建一个字典用于记录每个节点的最小距离g_scores= {start: 0} # 创建一个字典用于记录每个节点的父节点parents= {start: None} # 创建一个列表用于记录已经遍历过的节点closed_list=set() # 遍历开放列表，直到找到终点或开放列表为空whileopen_list: # 取出启发式估价最小的节点_, g_score, current, path=heapq.heappop(open_list) # 如果该节点已经被遍历过，则跳过ifcurrentinclosed_list: continue# 如果该节点是终点，则返回路径ifcurrent==end: returnpath+ [current] # 将该节点标记为已遍历，并将其所有相邻节点加入开放列表closed_list.add(current) forrow, colin ((current[0] -1, current[1]), (current[0] +1, current[1]), (current[0], current[1] -1), (current[0], current[1] +1)): ifrow<0orrow>=rowsorcol<0orcol>=colsormaze[row][col] =='X': continueneighbor= (row, col) tentative_g_score=g_score+1ifneighboring_scoresandtentative_g_score>=g_scores[neighbor]: continueparents[neighbor] =currentg_scores[neighbor] =tentative_g_scoref_score=tentative_g_score+heuristic_cost_estimate(neighbor, end) heapq.heappush(open_list, (f_score, tentative_g_score, neighbor, path+ [current])) # 如果起点到终点没有可达路径，则返回 NonereturnNone# 测试maze= [ ['S', ' ', ' ', ' ', 'X', ' ', 'X', ' ', 'X'], ['X', 'X', ' ', 'X', 'X', ' ', ' ', ' ', 'X'], ['X', 'X', ' ', ' ', ' ', ' ', ' ', 'X', ' '], ['X', ' ', 'X', 'X', 'X', ' ', 'X', ' ', 'X'], [' ', ' ', ' ', ' ', ' ', ' ', ' ', 'X', 'X'], ['X', ' ', 'X', ' ', 'X', ' ', ' ', ' ', 'X'], ['X', 'X', ' ', 'X', ' ', ' ', 'X', ' ', ' '], [' ', ' ', ' ', 'X', 'X', 'X', 'X', ' ', 'X'], ['X', ' ', ' ', ' ', ' ', 'X', 'X', 'E', ' '], ] start= (0, 0) end= (8, 7) shortest_path=a_star(maze, start, end) ifshortest_path: print(shortest_path) # 输出
在该代码中，a_star 函数接收三个参数：迷宫 maze，起点 start，和终点 end。该函数首先初始化一些数据结构，如开放列表、最小距离字典、父节点字典和已遍历节点集合等。然后将起点加入开放列表，并开始循环遍历开放列表，直到找到终点或开放列表为空。在遍历过程中，首先取出启发式估价最小的节点，并判断该节点是否已经被遍历过。如果已经被遍历过，则跳过；否则，将其标记为已遍历，并将其所有相邻节点加入开放列表。在处理相邻节点时，需要考虑它们是否越界或者是墙，以及到达该节点的最小距离是否已经被记录下来，如果已经记录且比当前距离更短，则跳过该节点。如果到达了终点，则返回从起点到终点的最短路径；否则，如果起点到终点没有可达路径，则返回 None。
在该代码中，heuristic_cost_estimate 函数用于计算从当前节点到终点的启发式估价函数值，它采用曼哈顿距离（也叫城市街区距离）来估算两点之间的距离，即两点横坐标差的绝对值加上两点纵坐标差的绝对值。该函数的目的是为了尽量减少遍历节点的数量，因为通过合理地选择启发式函数，可以尽早地排除掉不必要的节点，从而加快搜索速度。
该代码还使用了 Python 内置的 heapq 模块来实现优先队列，其中 heappush 和 heappop 分别用于向队列中添加元素和取出队列中的最小元素。同时，该代码还定义了一个辅助函数 heuristic_cost_estimate，用于计算从当前节点到终点。
带积分的最短路径
如果我们要是在迷宫中设置积分，在找到最短路径的时候，还需要拿到最高分，又应该怎么做呢？
第一种方法是可以修改启发式函数，使其考虑到节点的得分情况。例如，可以定义一个新的函数heuristic_cost_estimate_with_score(start, end, score_dict)，其中score_dict是一个字典，包含每个节点的得分。您可以将每个节点的得分作为额外的代价加入到启发式估价中。这样，算法将优先探索具有更高得分的节点，从而增加获得最高分的机会。
defheuristic_cost_estimate_with_score(start, end, score_dict): # 定义启发式函数returnabs(end[0] -start[0]) +abs(end[1] -start[1]) +score_dict.get(start, 0)
第二种方法，我们可以修改tentative_g_score计算方式以考虑到节点得分。例如，将节点得分乘以一个系数，如0.1，然后将其加到路径长度中。这样，算法将更倾向于选择具有更高得分的节点。
二维矩阵中找到所有的连通块
下面这段代码的目的是实现在二维矩阵中找到所有的连通块，并将它们以列表的形式返回。其中，连通块是由相邻的非零元素组成的，每个元素只与其上下左右四个方向上的元素相邻。算法使用广度优先搜索，对于每个未被遍历的非零元素，将其所在的连通块找出来，然后将其加入到结果列表中。
defbfs_connected_components(grid): # 初始化连通块列表connected_components= [] # 初始化visited列表，标记哪些单元格已被遍历过visited= [[Falsefor_inrange(len(grid[0]))] for_inrange(len(grid))] # 遍历每个单元格foriinrange(len(grid)): forjinrange(len(grid[0])): # 如果当前单元格未被遍历过且其值为非零ifnotvisited[i][j] andgrid[i][j] !=0: # 初始化当前连通块current_cc= [] # 将当前单元格加入当前连通块current_cc.append((i, j)) # 将当前单元格标记为已遍历visited[i][j] =True# 初始化待遍历队列，将当前单元格加入队列queue= [(i, j)] # 广度优先搜索whilequeue: # 取出队首单元格row, col=queue.pop(0) # 遍历其相邻的四个单元格ford_row, d_colin [(0, -1), (0, 1), (-1, 0), (1, 0)]: neighbor_row=row+d_rowneighbor_col=col+d_col# 如果相邻单元格在网格内且未被遍历过且其值为非零if (0<=neighbor_row<len(grid) and0<=neighbor_col<len(grid[0]) andnotvisited[neighbor_row][neighbor_col] andgrid[neighbor_row][neighbor_col] !=0): # 将相邻单元格加入当前连通块和待遍历队列current_cc.append((neighbor_row, neighbor_col)) queue.append((neighbor_row, neighbor_col)) # 标记相邻单元格为已遍历visited[neighbor_row][neighbor_col] =True# 将当前连通块加入连通块列表connected_components.append(current_cc) returnconnected_componentsdefmain(): grid= [ [1, 0, 1, 0], [1, 1, 0, 0], [0, 0, 1, 0], [1, 1, 0, 1] ] connected_components=bfs_connected_components(grid) print("Connected components:") forccinconnected_components: print(cc) if__name__=="__main__": main()
如果转换为具体的逻辑，可以按照下文理解：
- 初始化一个空的连通块列表和一个visited列表，visited列表用于标记哪些单元格已经被遍历过。
- 对于矩阵中的每个单元格，如果它没有被遍历过且其值不为零，就将其所在的连通块找出来。
- 找到一个未被遍历的非零元素后，初始化一个空的当前连通块列表current_cc，并将该元素加入到当前连通块列表和待遍历队列中。
- 使用广度优先搜索遍历待遍历队列中的元素，将其相邻的未被遍历的非零元素加入当前连通块列表和待遍历队列中，标记这些元素已被遍历过。
- 当待遍历队列为空时，当前连通块已经找到完毕，将其加入到连通块列表中。
- 重复步骤2-5直到所有未被遍历的非零元素所在的连通块都被找到为止。
- 返回连通块列表。
实际应用
BFS算法的主要应用是在无权图或有向无环图中查找最短路径，也可以用于生成迷宫、遍历树等问题。BFS算法通常使用队列来实现，它通过维护一个队列来存储待访问的节点，初始时将根节点入队，然后执行循环，每次从队列的头部取出一个节点进行访问，并将其相邻节点入队，直到队列为空或者找到目标节点为止。
