python 深度优先搜索
时间: 2023-07-21 07:42:48 浏览: 39
Python 中可以使用递归实现深度优先搜索(DFS),也可以使用栈来实现。下面是一个使用递归实现 DFS 的示例:
```python
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for next in graph[start] - visited:
dfs(graph, next, visited)
return visited
```
其中,graph 是一个字典,key 表示节点,value 表示与该节点相邻的节点集合。start 表示起始节点,visited 是一个记录已访问过的节点的集合。在每次访问一个节点时,都将该节点加入 visited 集合,并输出该节点。然后递归访问与该节点相邻且未访问过的节点。最后返回 visited 集合,表示遍历过的所有节点。
使用示例:
```python
graph = {'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])}
dfs(graph, 'A')
```
输出:
```
A
B
D
E
F
C
```
这是一个简单的深度优先搜索示例,实际应用中需要根据具体情况进行相应的调整。