dfs递归实现python
时间: 2023-08-24 12:06:11 浏览: 41
DFS(深度优先搜索)的递归实现可以用以下 Python 代码实现:
```python
# 定义图的邻接表表示法
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
visited = set() # 用集合记录已经访问过的节点
def dfs(node):
visited.add(node) # 将当前节点标记为已访问
print(node, end=' ') # 输出当前节点
for next_node in graph[node]:
if next_node not in visited:
dfs(next_node) # 递归访问下一个节点
# 从图的起始节点开始搜索
dfs('A')
```
这段代码实现了从图的起始节点 A 开始进行深度优先搜索(DFS),并输出搜索的路径。其中,`graph` 变量定义了图的邻接表表示法,`visited` 变量用集合记录已经访问过的节点,`dfs()` 函数实现了递归访问节点的过程。在访问一个节点时,先将其标记为已访问,然后输出该节点,并递归地访问该节点的所有邻居节点。
相关问题
python dfs递归实现迷宫问题
好的,下面是 Python 中 DFS 递归实现迷宫问题的代码示例:
```python
# 定义迷宫地图,0 表示可走,1 表示障碍物
maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 1, 0],
]
# 定义迷宫大小
n = len(maze)
m = len(maze[0])
# 定义标记数组,标记每个位置是否已经访问过
visited = [[False] * m for _ in range(n)]
# 定义终点位置
end = (4, 3)
# 定义方向数组,表示上下左右四个方向
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def dfs(x, y):
# 如果当前位置就是终点位置,则直接返回 True
if (x, y) == end:
return True
# 标记当前位置已经访问过
visited[x][y] = True
# 枚举四个方向
for dx, dy in directions:
nx, ny = x + dx, y + dy
# 判断是否越界,是否已经访问过,是否是障碍物
if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and maze[nx][ny] == 0:
# 递归搜索下一个位置
if dfs(nx, ny):
return True
# 如果四个方向都没找到终点,则返回 False
return False
# 在起点位置开始搜索
start = (0, 0)
if dfs(start[0], start[1]):
print("可以到达终点!")
else:
print("无法到达终点!")
```
这段代码中,我们先定义了一个迷宫地图 `maze`,然后定义了迷宫的大小 `n` 和 `m`,以及标记数组 `visited` 和终点位置 `end`。
接着,我们定义了一个 DFS 函数 `dfs`,它的参数是当前位置的坐标 `(x, y)`,表示从这个位置开始搜索。
在 `dfs` 函数中,我们首先判断当前位置是否是终点位置,如果是,则直接返回 True。
然后,我们标记当前位置已经访问过,并枚举当前位置可以走的四个方向。对于每个方向,我们判断是否可以走,如果可以,则递归搜索下一个位置。如果在四个方向中找到了终点位置,则返回 True。
最后,在主函数中,我们从起点位置开始搜索,如果可以到达终点,则输出“可以到达终点!”;否则输出“无法到达终点!”。
Dfs算法的递归实现
以下是DFS算法的递归实现:
```python
# 定义一个图的类
class Graph:
def __init__(self, graph_dict=None):
if graph_dict is None:
graph_dict = {}
self.__graph_dict = graph_dict
# 添加节点
def add_node(self, node):
if node not in self.__graph_dict:
self.__graph_dict[node] = []
# 添加边
def add_edge(self, edge):
edge = set(edge)
(node1, node2) = tuple(edge)
if node1 in self.__graph_dict:
self.__graph_dict[node1].append(node2)
else:
self.__graph_dict[node1] = [node2]
# DFS算法的递归实现
def dfs(self, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for next_node in self.__graph_dict[start]:
if next_node not in visited:
self.dfs(next_node, visited)
return visited
# 创建一个图
graph = Graph()
# 添加节点
graph.add_node('A')
graph.add_node('B')
graph.add_node('C')
graph.add_node('D')
graph.add_node('E')
graph.add_node('F')
# 添加边
graph.add_edge(('A', 'B'))
graph.add_edge(('A', 'C'))
graph.add_edge(('B', 'D'))
graph.add_edge(('B', 'E'))
graph.add_edge(('C', 'F'))
# 执行DFS算法
graph.dfs('A')
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![py](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)