深度优先搜索 python
时间: 2023-10-12 17:06:19 浏览: 115
python实现深度优先遍历搜索(DFS)算法-源码
深度优先搜索(Depth First Search, DFS)是一种用于遍历或搜索树或图的算法。在Python中,可以使用递归或栈来实现深度优先搜索。
以下是一个使用递归实现深度优先搜索的示例代码:
```python
def dfs(graph, node, visited):
if node not in visited:
print(node)
visited.add(node)
neighbors = graph[node]
for neighbor in neighbors:
dfs(graph, neighbor, visited)
# 示例图的邻接表表示
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
visited = set()
dfs(graph, 'A', visited)
```
这段代码会按照深度优先的顺序遍历并打印图中的节点。其中,`graph` 是图的邻接表表示,`node` 是当前节点,`visited` 是已经访问过的节点集合。在每次递归调用时,我们检查当前节点是否已经被访问过,如果没有,则将其加入到已访问集合中,并递归地对其未访问的邻居节点进行深度优先搜索。
希望这个示例对你有帮助!如果你还有其他问题,请随时提问。
阅读全文