0Pricing
Competitive Programming Academy · 课时

DFS、递归与迭代栈

深入探索并避开递归深度限制

DFS、递归与迭代栈 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。

DFS 的作用

DFS 会沿着一条路径尽可能深入，然后回退并尝试下一条路径。您可以把它想象成逐条走过迷宫中的通道。🧭

DFS 与 BFS

BFS 按环状层次扩散；DFS 则先深入到底。两者都会访问所有可达节点，但访问顺序截然不同。

递归结构

递归 DFS 会将节点标记为已访问，然后对每个尚未访问的邻居调用自身。调用栈会记住返回位置。

def dfs(u):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(v)

递归前标记

进入节点时就设置已访问标记，然后再探索邻居。否则，环会让 DFS 陷入无限递归。

递归限制陷阱

Python 将递归深度限制在约 1000 次调用以内。深层图会触发 RecursionError，并显示为运行时错误结果。

提高限制

一个快速解决办法是使用 setrecursionlimit 提高上限。在运行 DFS 之前，将它设置为大于最坏情况深度的值。

import sys
sys.setrecursionlimit(300000)

改用迭代方式

最安全的解决办法是使用自己的栈实现迭代式 DFS。不依赖调用深度，就永远不会发生递归崩溃。

stack = [start]

从栈中弹出

每一步都弹出栈顶元素。后进先出会让 DFS 优先沿着最近加入的路径深入。

u = stack.pop()

压入邻居

弹出 u 后，将每个尚未访问的邻居压入栈中。请为它们设置标记，避免再次压入。

for v in adj[u]:
    if not visited[v]:
        visited[v] = True
        stack.append(v)

完整的迭代循环

只要栈中还有节点，就重复弹出和压入操作。栈为空时，所有可达节点都已经访问完毕。

while stack:
    u = stack.pop()
    for v in adj[u]:
        if not visited[v]:
            visited[v] = True
            stack.append(v)

复杂度与 BFS 相同

与 BFS 一样，DFS 会恰好访问每个节点和每条边一次，因此运行时间为 O(n + m)。请根据任务需要的访问顺序进行选择。

快速检查

您的递归 DFS 在深层图上崩溃了。为什么？

回顾

您可以递归运行 DFS，也可以使用自己的栈；在进入节点时标记已访问，并在图较深时切换为迭代方式。🎉

常见问题解答

「DFS、递归与迭代栈」课时是免费的吗？

是的 — 「DFS、递归与迭代栈」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。

「DFS、递归与迭代栈」这节课中我会学到什么？

深入探索并避开递归深度限制 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Competitive Programming Academy 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。

「DFS、递归与迭代栈」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Competitive Programming Academy 课中编写并运行代码吗？

能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

  1. 从输入构建邻接表
  2. 使用 BFS 求无权最短路径
  3. DFS、递归与迭代栈
  4. 连通分量与洪水填充
← 返回 Competitive Programming Academy