深度优先搜索算法 (DFS)

7.1 DFS 算法的工作原理

深度优先搜索 (Depth-First Search, DFS) 是一种图遍历或搜索算法。 它从初始顶点开始，一直向图的深处探索，直到达到没有未访问邻居的顶点， 然后回溯并从其他顶点继续这个过程。

算法步骤：

1. 从选定的初始顶点开始，并标记为已访问。
2. 探索第一个未访问的邻接顶点。
3. 对该邻居重复步骤 1 和 2。
4. 如果当前顶点的所有邻居都被访问过，则回溯到前一顶点并继续这一过程。
5. 这个过程持续到所有从初始顶点可达的顶点都被访问。

可视化：

DFS 的时间和空间复杂度：

时间复杂度：

O(V + E)，其中 V 是顶点数量，E 是边的数量。

图的每个节点和每条边都被访问一次。

空间复杂度：

O(V)，因为需要调用栈或显式栈来存储顶点，以及用于存储状态的数组（已访问顶点）。

7.2 使用递归实现 DFS

我们先用递归来实现 DFS —— 代码会显得美观且简洁。

递归实现的 DFS：

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # 节点处理
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)
    
# 使用示例：
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_recursive(graph, 'A')

7.3 使用栈实现 DFS

不使用递归时，代码会稍微长一些，因为我们需要另外存储访问过的顶点列表。

迭代实现的 DFS（使用栈）：

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
        
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # 节点处理
        
            for neighbor in reversed(graph[vertex]):  # 反转顺序以保持正确的遍历顺序
                if neighbor not in visited:
                    stack.append(neighbor)
        
# 使用示例：
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_iterative(graph, 'A')

7.4 使用 DFS 解决的示例问题

使用 DFS 解决的经典示例问题：

1. 迷宫路径查找：

用于从起点到终点找到迷宫中的路径。

应用：

在电子游戏和机器人技术中用于穿越迷宫和复杂空间。

2. 图的连通性检查：

检查图是否连通（是否存在两顶点之间的路径）。

应用：

在网络分析中检查网络的连通性。

3. 拓扑排序：

用于对有向无环图 (DAG) 的顶点进行排序，以便在任何边 (u, v) 中顶点 u 在顶点 v 之前。

应用：

在编译器中用于排序依赖关系和任务。

4. 图中环检测：

检查图是否包含环。

应用：

在依赖性分析中检测循环依赖。

5. 迷宫生成：

使用 DFS 生成随机迷宫。

应用：

在游戏和娱乐应用中创建迷宫。