数据结构深度优先搜索
时间: 2023-12-30 11:23:35 浏览: 43
深度优先搜索(DFS)是一种用于搜索图或树的算法。它的基本思想是从起始节点开始,尽可能深地探索每个分支,直到无法继续下去,然后回溯到上一个节点,继续探索其他分支。这种搜索方式类似于探险者在迷宫中的行走方式,先选择一条路径,直到走到尽头,然后返回上一个节点,选择另一条路径继续探索。
深度优先搜索的算法步骤如下:
1. 从起始节点开始,将其标记为已访问。
2. 对于当前节点的每个未访问的邻居节点,递归地应用深度优先搜索算法。
3. 如果当前节点没有未访问的邻居节点,回溯到上一个节点。
4. 重复步骤2和步骤3,直到所有节点都被访问。
下面是一个深度优先搜索的示例:
```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 neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
# 从起始节点开始进行深度优先搜索
dfs('A')
```
输出结果为:A B D E F C