HOME

深度优先搜索的基本思想

什么是深度优先搜索？

深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索树或图数据结构的技术。它的基本思想是尽可能深入地探索每一个分支，直到不能再深入为止，然后再回溯到上一个节点，继续探索未访问的分支。

基本原理

递归实现

深度优先搜索通常通过递归函数来实现。该算法从给定的起始节点开始，并将其标记为已访问，然后遍历其所有相邻节点（即邻接点）。对于每一个相邻节点，如果它未被访问过，则重复执行上述操作；否则跳到下一个未访问的相邻节点。

非递归实现

非递归版本通常使用栈来保存待探索的节点。首先将起始节点加入栈中，然后从栈顶取出一个节点进行处理，并标记为已访问。接着遍历该节点的所有邻接点，如果这些邻接点未被访问过，则将其压入栈中。重复上述过程直到栈为空。

搜索流程

初始化：选择起始节点并标记它为已访问。
搜索当前节点的未访问邻居：对于当前节点的所有未访问过的相邻节点，递归地应用深度优先搜索算法。
回溯操作：当所有从当前节点出发的路径都被探索过后，返回到上一个节点继续探索。

示例

假设有一个包含四个节点A、B、C和D的图，并且它们之间的连接如下：

A -> B
A -> C
C -> D

递归实现

def dfs(node, visited):
    if node not in visited:
        print(node)
        visited.add(node)
        for neighbor in graph[node]:
            dfs(neighbor, visited)

visited = set()
dfs('A', visited)

非递归实现

from collections import deque

def dfs(start_node):
    stack = [start_node]
    visited = set()

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node)
            visited.add(node)
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

dfs('A')

应用场景

深度优先搜索适用于以下情况：

当搜索目标是找到一个路径时，如迷宫问题或图的连通性检查。
在游戏领域中用于生成随机地图布局。

通过这些基本思想和实现方法的理解，我们可以更有效地使用DFS来解决各种复杂的问题。