python用栈深度优先搜索
时间: 2024-03-14 15:42:18 浏览: 16
在Python中,可以使用栈来实现深度优先搜索(DFS)。深度优先搜索是一种用于遍历或搜索图或树的算法,它从起始节点开始,沿着一条路径尽可能深入地探索,直到无法继续为止,然后回溯到前一个节点,继续探索其他路径。
下面是一个使用栈实现深度优先搜索的示例代码:
```python
def dfs(graph, start):
visited = set() # 用于记录已访问的节点
stack = [start] # 使用栈来保存待访问的节点
while stack:
node = stack.pop() # 弹出栈顶节点
if node not in visited:
print(node) # 访问节点
visited.add(node)
neighbors = graph[node] # 获取当前节点的邻居节点
stack.extend(neighbors) # 将邻居节点加入栈中
# 示例图的邻接表表示
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
dfs(graph, 'A')
```
上述代码中,我们使用一个集合`visited`来记录已经访问过的节点,使用一个栈`stack`来保存待访问的节点。首先将起始节点加入栈中,然后进入循环,每次从栈中弹出一个节点,如果该节点未被访问过,则进行访问,并将其标记为已访问。然后将该节点的邻居节点加入栈中,继续下一轮循环。直到栈为空时,搜索结束。