深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树和图的算法。在最坏的情况下,深度优先搜索的性能为 O(V+E),其中 V 是顶点数,E 是边数。DFS 常用于解决连通性问题、路径问题、生成树问题等。

DFS 的使用步骤

  1. 初始化:创建一个数据结构(如栈)来存储遍历过程中访问的节点。

  2. 访问起始节点:将起始节点添加到栈中,并标记为已访问。

  3. 探索邻居:从栈顶取出一个节点,检查其所有未访问的邻居节点。

  4. 递归或迭代:对每一个未访问的邻居节点,将其添加到栈中,并将其标记为已访问。

  5. 重复探索:重复步骤 3 和 4,直到栈为空。

  6. 结束条件:当栈为空且没有更多节点可以访问时,搜索结束。

DFS 的实现

DFS 可以用递归或非递归(迭代)的方式实现。

递归实现

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node)  # 处理节点
    for neighbour in graph[node]:
        if neighbour not in visited:
            dfs(graph, neighbour, visited)
    return visited

非递归实现(使用栈)

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node)  # 处理节点
            visited.add(node)
            stack.extend(graph[node] - visited)  # 添加未访问的邻居到栈中
    return visited

DFS 的深度优化

  1. 剪枝:在搜索过程中,如果确定某个节点不可能产生有效结果,可以提前终止对该节点的搜索。

  2. 启发式搜索:在搜索过程中使用启发式信息来指导搜索方向,减少搜索空间。

  3. 迭代加深:结合 DFS 和 BFS 的优点,通过限制搜索深度来减少内存使用,并在必要时增加深度。

  4. 使用位图或哈希表:使用位图或哈希表来快速检查节点是否已访问。

  5. 优化邻接表存储:使用合适的数据结构来存储图的邻接表,如邻接表或邻接矩阵,根据实际情况选择。

  6. 并行搜索:在多处理器或多线程环境中,可以并行地执行 DFS 搜索。

实战案例

假设我们要在一个图中找到一个节点到另一个节点的路径。

  1. 构建图:首先,根据问题描述构建图的邻接表。

  2. 调用 DFS:从起始节点开始调用 DFS 函数。

  3. 回溯:在 DFS 中,如果当前路径包含了目标节点,记录路径并回溯。

  4. 路径恢复:通过回溯过程,可以从栈或递归调用链中恢复路径。

通过 DFS,可以有效地找到图中的路径,解决许多图论问题。在实际应用中,根据问题的特点和约束,可以对 DFS 进行适当的优化,以提高搜索效率。本篇只是入门级的,更深层次的应用,后面会持续更新,欢迎大家提意见!!!


↙↙↙阅读原文可查看相关链接,并与作者交流