Python 中的深度优先搜索：遍历图与树

想象您在探索一个庞大的洞穴系统。您选择一条通道，沿着它不断深入，直到抵达尽头。然后，您退回到最近的分叉口，再尝试一条新通道。这种尽可能深入探索、只在必要时回溯的方式，很像深度优先搜索（DFS）——一种用于在图和树等数据结构中导航的基础算法。

如果您对数据结构、算法与问题求解感兴趣，DataCamp 能满足您的需求：在 Data Structures and Algorithms in Python 课程和我们的 Data Structures: A Comprehensive Guide With Python Examples 教程中，了解不同的数据结构以及探索它们的最佳算法。

什么是深度优先搜索？

深度优先搜索（DFS）是一种用于遍历或搜索数据结构（如图或树）的算法。DFS 的基本思想是：在回溯以探索其他分支之前，尽可能沿着图或树的某个分支向下探索。这与广度优先搜索形成对比，后者会先探索当前深度层的所有节点，然后再进入下一层。您可以在此处阅读关于广度优先搜索的介绍 HERE。

把深度优先搜索想象成探索迷宫：您选择一条路径并沿着它走到尽头。一旦到达这条路径的终点，您便回溯到上一个决策点，尝试不同的路线。这种深入探索的特性，让 DFS 在需要彻底探索结构、尤其是可能路径很多的情况下，成为出色的选择。

DFS 在需要穷尽所有可能解的问题中特别有用。

例如：

• 在人工智能中的决策树导航，每个分支代表一连串选择，目标是评估所有可能结果。
• 路径寻优问题，例如在棋盘上行进或在地图上寻找路线，这些问题需要穷尽式的搜索。

DFS 确保每个节点都被访问一次，算法覆盖整个图或树。

Python 中深度优先搜索的关键特性

深度优先搜索以系统化方式探索节点，并且只在必要时回溯。下面我们来看它的一些关键特性。

递归特性

从根本上说，DFS 以递归方式工作，也就是在深入结构时不断自我调用。当 DFS 沿着某个分支下潜时，它会尽可能深入，然后再回到更高层去探索其他分支。对于这种沿路径深入、在没有更多选项时回溯的过程，递归是理想的处理方式。 参阅 Understanding Recursive Functions in Python，深入了解什么是递归函数以及何时使用它们。

回溯

回溯是 DFS 的关键。当算法到达一个没有未访问邻居的节点时，它会沿原路返回到前一个节点，检查那里是否还有未访问的邻居。如果有，就继续探索；如果没有，则继续回溯。这样不断深入与回溯，直到覆盖所有可能路径或满足退出条件。

处理环

图可能包含环，即会自我回路的路径。如果不加以防范，DFS 可能在这些环中无休止地重复访问节点。通过在节点首次被遇到时将其标记为已访问，DFS 可以避免不必要的重复溯回。这样，即使在有环的图中，DFS 依然高效并可避免无限循环。

全面探索

DFS 的一个标志性优势是其充分探索结构的能力。算法会持续运行，直到每个节点都被访问。这在需要确保不遗漏任何潜在解的场景中尤为有用，例如解谜、探索决策树或穿越迷宫。

在 Python 中实现深度优先搜索

在 Python 中实现深度优先搜索主要有两种方式：递归与迭代。每种方法各有优劣，选择通常取决于图的规模以及您要解决的问题。

为演示两种方法，我们先构建一个简单的决策树，并使用 DFS 遍历它。我们将以 Python 为例。如需回顾 Python 技能，可随时参加 Python Programming 技能路径学习。

我们以二叉决策树为例。下面是一个简单的树结构，每个节点都有两个子分支：

我们用 Python 的字典来显式定义这棵决策树。

# Define the decision tree as a dictionary
tree = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': ['H', 'I'],
    'E': ['J', 'K'],
    'F': ['L', 'M'],
    'G': ['N', 'O'],
    'H': [], 'I': [], 'J': [], 'K': [],
    'L': [], 'M': [], 'N': [], 'O': []
}技术支持

递归式 DFS

DFS 通常以递归方式实现。在每个节点，DFS 会对其子节点进行自我调用，直到没有可访问的节点，然后回溯。下面是一个用于遍历该树的递归 DFS 函数。

# Recursive DFS function
def dfs_recursive(tree, node, visited=None):
    if visited is None:
        visited = set()  # Initialize the visited set
    visited.add(node)    # Mark the node as visited
    print(node)          # Print the current node (for illustration)
    for child in tree[node]:  # Recursively visit children
        if child not in visited:
            dfs_recursive(tree, child, visited)

# Run DFS starting from node 'A'
dfs_recursive(tree, 'A')技术支持

在这个递归版本中，我们从根节点 A 出发，沿每个分支向下探索，然后回溯以探索其他分支。运行该代码，将输出遍历此树时经过的路径：

A
B
D
H
I
E
J
K
C
F
L
M
G
N
O技术支持

迭代式 DFS

对于非常大的决策树，Python 的递归深度限制可能带来问题。在这种情况下，我们可以用迭代方式实现 DFS，使用栈来管理待访问的节点。下面展示如何为同一棵决策树实现迭代式 DFS：

# Iterative DFS function
def dfs_iterative(tree, start):
    visited = set()  # Track visited nodes
    stack = [start]  # Stack for DFS

    while stack:  # Continue until stack is empty
        node = stack.pop()  # Pop a node from the stack
        if node not in visited:
            visited.add(node)  # Mark node as visited
            print(node)        # Print the current node (for illustration)
            stack.extend(reversed(tree[node]))  # Add child nodes to stack

# Run DFS starting from node 'A'
dfs_iterative(tree, 'A')技术支持

这种迭代方法通过手动管理栈来避免递归深度限制，对大型或很深的结构十分有用。运行该代码将得到与上文相同的输出。

何时选择递归式或迭代式 DFS

递归与迭代两种深度优先搜索方法都很有价值，但如何选择取决于图的结构及您的具体需求。让我们更详细地看看各自的优势与局限。

递归式 DFS

我通常偏爱递归式 DFS 的简洁与优雅。这种方式直观而清晰。

优点：

• 简单：代码紧凑，且与问题本身高度契合。
• 可读性：更易理解，尤其适用于小型到中等规模的问题。

缺点：

• 递归深度限制：对于大型图，您可能会触及 Python 的递归深度上限。

当树或图相对较小，且能轻松在 Python 的递归深度范围内处理时，递归是理想之选。

迭代式 DFS

尽管编写起来稍微复杂一些，迭代式 DFS 更灵活，能在不担心递归限制的情况下处理更大规模的问题。与其依赖 Python 的调用栈，迭代式 DFS 会显式使用栈来管理待探索的节点。

优点：

• 无递归限制：手动管理栈可避免 Python 的递归深度限制。

缺点：

• 代码更多：迭代式 DFS 需要更多设置，且不如递归直观。
• 可读性：代码通常更为啰嗦，略难于跟进。

当担心递归深度、或需要对遍历过程有更多控制时，迭代式方法更适合大型或复杂问题。

时间与空间复杂度

DFS 是一种高效算法，但其性能会受到所探索图的规模与结构影响。运行时间与内存使用取决于访问的节点数量及其相互连接方式。

我们使用 BigO 表示法来讨论复杂度。若需回顾 Big O 表示法，请参阅 Big O Notation and Time Complexity Guide: Intuition and Math。

时间复杂度

DFS 的时间复杂度为 O(V + E)，其中 V 是节点数，E 是连接数（称为“边”）。DFS 会将每个节点和每条连接访问一次。因此，总运行时间取决于节点与连接的数量。

空间复杂度

DFS 的空间使用取决于算法在任意时刻需要追踪的节点数量。递归与迭代式 DFS 都使用栈来追踪正在探索的节点。在最坏情况下，内存使用可能需要容纳图中的所有节点，空间复杂度为 O(V)。

在 Analyzing Complexity of Code through Python 教程中探索衡量算法复杂度的其他方法。

深度优先搜索的真实应用场景

DFS 广泛用于计算机科学、人工智能与游戏开发等诸多领域。请查看下表，了解一些常见的 DFS 应用。

深度优先搜索与其他搜索算法对比

让我们将 DFS 与其他知名算法比较，例如广度优先搜索、Dijkstra 算法与 A*。

深度优先搜索 vs. 广度优先搜索

广度优先搜索（BFS）按层次探索图，先访问当前深度的所有节点，再进入下一层。当目标是在无权图中寻找最短路径时，BFS 尤其有用。不过，BFS 在宽度很大的图中会占用大量内存，因为它必须跟踪每一层的所有节点。BFS 非常适合社交网络分析或简单的路由问题。

另一方面，当目标是探索所有可能路径或解（如解谜或在图中寻找环）时，深度优先搜索很有用。与 BFS 不同，DFS 不保证最短路径。但它更节省内存，因为它只需跟踪当前路径。

您可以在此处了解更多关于广度优先搜索的内容Breadth-First Search: A Beginner’s Guide with Python Examples。

DFS vs. Dijkstra 算法

Dijkstra 算法旨在寻找带权图中的最短路径，其中节点之间的每条连接都具有相关成本。Dijkstra 会优先探索代价最低的路径，确保从起点到任意节点的最优路径被找到。然而，在某些简单的图探索中，它可能比 DFS 更慢。对于边权重要的任务（如道路网络或更复杂的路由问题），Dijkstra 是理想之选。

深度优先搜索不考虑边权，因此无法保证最优路径。不过，在无权图或边权无关的情况下，它可能比 Dijkstra 更快。

您可以在 Implementing the Dijkstra Algorithm in Python: A Step-by-Step Tutorial 中了解更多 Dijkstra 算法。

DFS vs. A*

A*（读作“A-star”）在 Dijkstra 的基础上引入启发式以引导搜索，这使其在许多场景下更快更高效。A* 在探索代价最低的路径（类似 Dijkstra）与直接朝目标前进之间取得平衡，通常使用直线距离等启发式。这让 A* 在 GPS 导航或电子游戏路径寻优等任务中极为高效。

深度优先搜索不使用任何启发式，也就缺乏 A* 用于高效抵达目标的“方向感”。当需要对整个图或决策树进行彻底搜索时，DFS 更合适；而当需要借助启发式高效找到最短路径时，A* 更为理想。

常见陷阱及规避方法

在使用深度优先搜索时，尤其是在大型图中，可能会出现一些常见问题。

未追踪已访问节点

一个问题是忘记追踪哪些节点已被访问。这会导致无限循环，特别是在包含环的图中。如果 DFS 在不检查是否已被探索的情况下重新访问节点，就可能陷入死循环。为避免此问题，请务必维护一个已访问节点的集合。在访问新节点前，检查它是否已在已访问集合中；若已存在，便可安全跳过，从而避免陷入困境。

递归式 DFS 的栈溢出

在 Python 中，默认递归深度约为 1000 层，这意味着在大型图中非常深的递归调用会导致 RecursionError。为防止此问题，我们可以对大型图使用迭代式 DFS 实现。通过用列表维护这个栈，我们可以避开递归深度限制，从而安全地处理更大的图。

将某解误认为最短路径

还需牢记，DFS 不保证两个节点之间的最短路径。由于 DFS 会在回溯前深入沿着一条路径，它或许能找到一个解，但未必是最直接的那一个。

结语

深度优先搜索是一种强大的算法，可用于探索与遍历图和树。凭借其深入路径并穷尽探索的能力，它非常适合迷宫求解、解谜以及决策树探索等多种问题。

如果您对搜索算法感兴趣，欢迎阅读我在本系列中的其他文章： Binary Search in Python: A Complete Guide for Efficient Searching 与 Breadth-First Search: A Beginner’s Guide with Python Examples。您或许也会对 AVL Tree: Complete Guide With Python Implementation 和 Introduction to Network Analysis in Python 感兴趣。