深度优先搜索基本思想
时间: 2023-12-18 09:29:45 浏览: 35
深度优先搜索(DFS)是一种用于遍历或搜索树或图的算法。其基本思想是从根节点开始,沿着一条路径直到到达叶子节点,然后回溯到前一个节点,继续沿着另一条路径直到到达叶子节点,如此往复,直到遍历完整个树或图。在搜索过程中,每个节点都会被访问一次且仅访问一次,而且每个节点的子节点都会被优先访问。
具体来说,深度优先搜索的基本思想是:从起始节点开始,依次访问与其相邻的节点,如果当前节点还有未访问的相邻节点,则选择其中一个继续进行深度优先搜索,直到当前节点没有未访问的相邻节点为止,然后回溯到上一个节点,继续搜索其他未访问的相邻节点,直到所有节点都被访问为止。
在实际应用中,深度优先搜索常用于解决迷宫问题、拓扑排序、连通性问题等。
代码示例:
```python
# 以邻接表形式存储图
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# 深度优先搜索函数
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for next_node in graph[start]:
if next_node not in visited:
dfs(graph, next_node, visited)
# 调用深度优先搜索函数
dfs(graph, 'A')
```
输出结果为:A B D E F C