python深度优先搜索
时间: 2023-10-13 15:24:49 浏览: 41
深度优先搜索(Depth First Search,DFS)是一种用于遍历或搜索树或图的算法。该算法从根节点开始,尽可能深地探索每个节点的分支,直到无法继续为止,然后回溯到上一级节点,继续探索其他分支。
在Python中,可以使用递归函数来实现深度优先搜索。以下是一个简单的例子,使用深度优先搜索在一个无向图中查找从1到7的路径:
```python
# 定义图的邻接表表示法
graph = {
1: [2, 3],
2: [1, 4, 5],
3: [1, 6, 7],
4: [2],
5: [2],
6: [3],
7: [3]
}
# 定义深度优先搜索函数
def dfs(node, visited, end):
if node == end:
return [node]
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
path = dfs(neighbor, visited, end)
if path:
return [node] + path
return []
# 在图中查找从1到7的路径
print(dfs(1, set(), 7)) # 输出:[1, 3, 7]
```
在上面的代码中,dfs函数接受三个参数:当前节点node、已访问过的节点集合visited和目标节点end。如果当前节点是目标节点,则返回[node],表示找到了一条路径。否则,将当前节点加入visited集合中,并遍历当前节点的所有邻居节点。对于每个未访问过的邻居节点,递归调用dfs函数,并将返回值与[node]连接起来,得到一条从当前节点到目标节点的路径。如果找到了一条路径,则直接返回路径;否则,返回空列表[],表示在当前节点无法找到从当前节点到目标节点的路径。