一、深度优先搜索
深度优先搜索(DFS)是一种用于图遍历或树遍历的算法。它的核心思想是尽可能地向深度方向遍历,直到到达最深处,然后返回上一个节点,继续向另一个方向遍历。
深度优先搜索的实现可以使用递归或栈(迭代版本)来实现。以下是递归实现的示例代码:
# 使用邻接列表表示图graph = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F'],'D': [],'E': ['F'],'F': []}visited = set() # 用于记录已经访问过的节点def dfs(node):if node not in visited:print(node)visited.add(node)for neighbor in graph[node]:dfs(neighbor)dfs('A')
在这个示例中,dfs
函数递归地遍历邻接列表表示的图。如果当前节点没有被访问过,则输出该节点,将其添加到已访问集合中,并递归访问其邻居节点。
下面是使用栈实现深度优先搜索的示例代码:
# 使用邻接列表表示图graph = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F'],'D': [],'E': ['F'],'F': []}visited = set() # 用于记录已经访问过的节点def dfs(start):stack = [start]while stack:node = stack.pop()if node not in visited:print(node)visited.add(node)for neighbor in graph[node]:stack.append(neighbor)dfs('A')
在这个示例中,dfs
函数使用栈来实现深度优先搜索。它从起始节点开始,将其入栈。然后进入一个循环,弹出栈顶节点,如果该节点没有被访问过,则输出该节点,将其添加到已访问集合中,并将其邻居节点压入栈中。循环继续,直到栈为空。
题目背景
给定一个N*M方格的迷宫,迷宫里有T处障碍,障碍处不可通过。给定起点坐标和终点坐标,问: 每个方格最多经过1次,有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式,每次只能移动一个方格。数据保证起点上没有障碍。
这是一个典型的搜索问题,可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来解决。由于题目中给定了障碍,所以在搜索过程中需要判断当前位置是否是障碍,如果是则不能继续搜索。
下面以DFS为例,给出一个可能的实现:
def dfs(x, y, visited, end_x, end_y, maze):if x == end_x and y == end_y:return 1visited[x][y] = Truecount = 0for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:new_x, new_y = x + dx, y + dyif 0 <= new_x < len(maze) and 0 <= new_y < len(maze[0]) and not visited[new_x][new_y] and not maze[new_x][new_y]:count += dfs(new_x, new_y, visited, end_x, end_y, maze)visited[x][y] = Falsereturn countdef num_paths(start_x, start_y, end_x, end_y, maze):visited = [[False]*len(maze[0]) for _ in range(len(maze))]return dfs(start_x, start_y, visited, end_x, end_y, maze)
其中,dfs
函数表示从当前位置开始搜索,已经访问过的位置保存在visited
中,终点坐标是(end_x, end_y)
,maze
表示整个迷宫。num_paths
函数是最终的接口函数,用于调用dfs
函数并返回结果。
需要注意的是,在搜索过程中,已经访问过的位置需要标记为已访问,避免重复搜索,但在返回时需要将其标记为未访问,以允许其他路径从该位置经过。另外,在搜索时需要判断当前位置是否越界或是障碍,避免出现数组下标越界或是走到障碍的情况。
二、广度优先搜索
广度优先搜索(Breadth-First Search,BFS)是一种基于图形数据结构的算法,用于解决从起点到目标节点的最短路径问题。BFS以图形结构为基础,逐层搜索与起点相邻的节点,并且保持搜索距离一层一层地增加,直到找到目标节点或者遍历完所有节点。
下面是广度优先搜索的实现步骤:
定义一个队列Q,并将起点节点放入队列中。将起点节点标记为已访问。从队列中弹出节点并检查该节点是否为目标节点,如果是,则结束搜索。如果不是目标节点,则将该节点的所有未访问过的相邻节点加入队列中,并标记它们为已访问。重复步骤3-4,直到找到目标节点或者遍历完所有节点。
BFS算法可以使用迭代或者递归的方式进行实现。以下是Python中使用队列实现BFS算法的非递归实现:
from collections import dequedef bfs(graph, start):visited = set() # 用集合来存储已访问过的节点queue = deque([start]) # 使用双向队列来存储待访问的节点visited.add(start) # 标记起始节点为已访问while queue:vertex = queue.popleft() # 取出队列中的第一个节点print(vertex, end=" ")for neighbor in graph[vertex]: # 遍历该节点的所有邻居节点if neighbor not in visited: # 如果邻居节点没有被访问过visited.add(neighbor) # 标记为已访问queue.append(neighbor) # 将邻居节点加入队列
其中,graph
参数为图的邻接表表示,start
参数为起始节点。在该实现中,使用了Python标准库中的deque
类来实现队列的功能,同时使用了Python的set
类来存储已访问的节点,以避免重复访问。bfs
函数中的while循环用于不断地取出队列中的节点进行访问,直到队列为空为止。
递归方式实现BFS也是可行的。递归方式的BFS可以看作是一个深度优先搜索(DFS)的变种,它通过使用队列来保存每一层的节点,从而实现了广度优先的搜索方式。BFS算法通常使用非递归实现,但是在某些情况下也可以使用递归实现,例如对于较小的图。
以下是BFS算法的Python递归实现:
from collections import dequedef bfs(graph, queue, visited):if not queue:returnnode = queue.popleft()print(node)for neighbor in graph[node]:if neighbor not in visited:queue.append(neighbor)visited.add(neighbor)bfs(graph, queue, visited)# 以字典形式表示图graph = {'A': ['B', 'D'],'B': ['A', 'C', 'F'],'C': ['B', 'F'],'D': ['A', 'E'],'E': ['D', 'F'],'F': ['B', 'C', 'E'],}# 创建空队列和集合,并将起始节点加入队列和集合queue = deque(['A'])visited = set(['A'])# 调用递归函数bfs(graph, queue, visited)
在递归实现中,我们定义了一个名为bfs
的递归函数,它接受三个参数:graph
表示图的字典,queue
表示当前要访问的节点队列,visited
表示已访问过的节点集合。
首先,我们从队列中取出队首节点,并打印该节点的值。然后,我们遍历该节点的邻居节点,并将邻居节点添加到队列中,并将其标记为已访问。最后,我们递归调用bfs
函数,以便继续遍历下一个节点。
在主程序中,我们首先创建空队列和集合,并将起始节点加入队列和集合。然后,我们调用bfs
函数,以开始遍历整个图。
需要注意的是,递归方式实现BFS的性能通常不如迭代方式实现BFS。因为递归会产生函数调用的开销,而队列的操作也会导致额外的内存开销。因此,在实际应用中,通常建议使用迭代方式实现BFS。
题目:
有一个 n×m 的棋盘,在某个点 (x,y) 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
题解:
这是一个典型的图论问题,可以使用广度优先搜索(BFS)来解决。
具体步骤如下:
创建一个二维数组dist
,用来记录每个点到马所在点的最短距离。初始化为全零。将马所在点加入一个队列q
中,同时将其dist
值设为0。对队列进行广度优先搜索。从队列中取出一个点,将其周围可以到达的点加入队列,并更新这些点的dist
值。注意,这里的“可以到达的点”是指棋盘上的合法位置,即横、纵坐标都在棋盘范围内,并且与当前点的横、纵坐标之差的绝对值之和为3。重复步骤3,直到队列为空。
最后,dist
数组中记录的就是每个点到马所在点的最短距离。
以下是Python代码实现:
from collections import dequedef min_steps(n, m, x, y):# 初始化dist数组dist = [[0] * m for _ in range(n)]# 将马所在点加入队列并标记dist值为0q = deque([(x, y)])dist[x][y] = 0# 广度优先搜索while q:cur_x, cur_y = q.popleft()for dx, dy in [(1, 2), (2, 1), (1, -2), (2, -1), (-1, 2), (-2, 1), (-1, -2), (-2, -1)]:next_x, next_y = cur_x + dx, cur_y + dyif 0 <= next_x < n and 0 <= next_y < m and dist[next_x][next_y] == 0:dist[next_x][next_y] = dist[cur_x][cur_y] + 1q.append((next_x, next_y))return dist
这个函数的输入参数为棋盘的行数n
、列数m
以及马所在点的横、纵坐标x
、y
。输出为一个二维数组,记录了每个点到马所在点的最短距离。
如果觉得《搜索算法——深度优先 广度优先》对你有帮助,请点赞、收藏,并留下你的观点哦!