OI-wiki 深度优先搜索DFS详解图遍历、递归与栈实现及竞赛应用【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读深度优先搜索Depth First SearchDFS是图论与算法竞赛中最基础也最核心的遍历算法之一OI-wiki 图论模块的 dfs.md 系统讲解了它的算法过程、复杂度性质、两种典型实现方式栈实现与递归实现以及 DFS 序列、括号序列、DFS 生成树等衍生概念。本文以该文档为骨架结合仓库中 图的存储、强连通分量 等关联文档与真实源码全面展开 DFS 的原理、实现与在竞赛算法中的应用。读完本文你将掌握 DFS 的完整理论框架、可直接运行的 C/Python/Java 实现以及它在树的直径、重心、割点、LCA、强连通分量等问题中的典型用法。引入什么是 DFSDFS 全称是 Depth First Search深度优先搜索是一种用于遍历或搜索树或图的算法。所谓深度优先就是指每次都尝试向更深的节点走从起点出发沿着一条路径尽可能深入地访问直到无法继续再回溯Backtrack到最近的分叉点尝试其他分支。该算法讲解时常常与 BFS广度优先搜索参见 docs/graph/bfs.md并列但两者除了都能遍历图的连通块以外用途完全不同很少有能混用两种算法的情况——BFS 擅长求无权图最短路等层次问题DFS 则天然契合递归结构与回溯搜索。需要特别区分的是OI 语境下DFS常被用来指代用递归函数实现的搜索即暴力枚举/回溯搜索但两者实际上并不一样。图论中的 DFS 是遍历图的确定算法而DFS搜索是利用递归函数方便地实现暴力枚举的思想详见 docs/search/dfs.md。算法过程DFS 最显著的特征在于其递归调用自身。同时与 BFS 类似DFS 会对其访问过的点打上访问标记visited 标记在遍历图时跳过已打过标记的点以确保每个点仅访问一次。符合以上两条规则递归调用 访问标记的函数便是广义上的 DFS。具体地说DFS 大致结构如下DFS(v) // v 可以是图中的一个顶点也可以是抽象的概念如 dp 状态等 在 v 上打访问标记 for u in v 的相邻节点 if u 没有打过访问标记 then DFS(u) end end end以上代码只包含了 DFS 必需的主要结构。实际的 DFS 会在以上代码基础上加入一些代码利用 DFS 性质进行其他操作例如记录dfn时间戳见割点/强连通分量章节、记录入栈/出栈顺序见括号序列章节、累加子树大小见树的遍历应用章节等。性质该算法通常的时间复杂度为 $O(nm)$空间复杂度为 $O(n)$其中 $n$ 表示点数$m$ 表示边数。注意空间复杂度包含了栈空间栈空间的空间复杂度是 $O(n)$ 的递归深度最坏情况下为 $n$。在平均 $O(1)$ 遍历一条边的条件下才能达到 $O(nm)$ 的时间复杂度例如用前向星或邻接表存储图如果用邻接矩阵则遍历一个点的出边需要 $O(n)$整体复杂度退化为 $O(n^2)$不一定能达到上述复杂度。备注算法竞赛中的栈空间目前大部分算法竞赛包括 NOIP、大部分省选以及 CCF 举办的各项赛事都支持无限栈空间即栈空间不单独限制但总内存空间仍然受题面限制。但大部分操作系统会对栈空间做额外的限制因此在本地调试时需要一些方式来取消栈空间限制。在 Windows 上通常的方法是在编译选项中加入-Wl,--stack1000000000表示将栈空间限制设置为 1000000000 字节。在 Linux 上通常的方法是在运行程序前在终端内执行ulimit -s unlimited表示栈空间无限。每个终端只需执行一次对之后每次程序运行都有效。这一点在编写深度较大的递归 DFS 时尤为重要即使评测环境支持无限栈空间本地调试时若不调整栈限制也可能因为系统默认的小栈空间如 Linux 通常为 8MB而直接栈溢出Stack Overflow。实现栈实现DFS 可以使用 栈Stack 为遍历中节点的暂存容器来实现这与用 队列Queue 实现的 BFS 形成高度对应——两者最大的区别仅在于从暂存容器中取出元素的方式DFS 取栈顶LIFO后进先出BFS 取队首FIFO先进先出。C使用std::stackvectorvectorint adj; // 邻接表 vectorbool vis; // 记录节点是否已经遍历 void dfs(int s) { stackint st; st.push(s); vis[s] true; while (!st.empty()) { int u st.top(); st.pop(); for (int v : adj[u]) { if (!vis[v]) { vis[v] true; // 确保栈里没有重复元素 st.push(v); } } } }Python用列表模拟栈# adj : List[List[int]] 邻接表 # vis : List[bool] 记录节点是否已经遍历 def dfs(s: int) - None: stack [s] # 用列表来模拟栈把起点加入栈中 vis[s] True # 起点被遍历 while stack: # 当栈非空时继续执行 u ( stack.pop() ) # 拿取并丢弃掉最后一个元素栈顶的元素可以理解为走到u这个元素 for v in adj[u]: # 对于与u相邻的每个元素v if not vis[v]: # 如果v在此前没有走过 vis[v] True # 确保栈里没有重复元素 stack.append(v) # 把v加入栈中需要注意栈实现中的一个关键细节入栈时立即标记vis[v] true而非出栈时才标记。这样可以确保栈中没有重复元素避免同一节点被多次入栈导致重复遍历是保证 $O(nm)$ 复杂度的前提。栈实现与递归实现最大的区别在于栈实现不会占用系统调用栈因此不受栈空间限制在递归深度极大如链式图深度可达 $10^6$ 级别时是更稳妥的选择。递归实现函数在递归调用时的求值如同对栈的添加和删除元素的顺序故函数调用所占据的虚拟地址被称为函数调用栈Call StackDFS 可用递归的方式实现——递归实现与上一节的栈实现本质是同一算法的两种写法。以 邻接表Adjacency List 作为图的存储方式Cvectorvectorint adj; // 邻接表 vectorbool vis; // 记录节点是否已经遍历 void dfs(const int u) { vis[u] true; for (int v : adj[u]) if (!vis[v]) dfs(v) }Python# adj : List[List[int]] 邻接表 # vis : List[bool] 记录节点是否已经遍历 def dfs(u: int) - None: vis[u] True for v in adj[u]: if not vis[v]: dfs(v)以 链式前向星 为例链式前向星本质上是用链表实现的邻接表遍历出边时从head[u]出发沿nxt指针链式访问Cvoid dfs(int u) { vis[u] 1; for (int i head[u]; i; i e[i].x) { if (!vis[e[i].t]) { dfs(v); } } }Javapublic void dfs(int u) { vis[u] true; for (int i head[u]; i ! 0; i e[i].x) { if (!vis[e[i].t]) { dfs(v); } } }Pythondef dfs(u): vis[u] True i head[u] while i: if vis[e[i].t] False: dfs(v) i e[i].x递归实现的优点是代码极简、与算法描述一一对应且便于在递归的前后位置插入自定义逻辑如记录dfn、low、子树大小等缺点则是递归深度受系统栈限制在深度极大的图中可能栈溢出需要配合上文提到的栈空间调整手段或改用显式栈实现。图的存储方式对 DFS 的影响从仓库中 docs/graph/save.md 可以系统对比几种存储方式对 DFS 遍历效率的影响存储方式遍历一个点的出边遍历整张图空间备注直接存边$O(m)$$O(nm)$$O(m)$遍历效率低一般不用于遍历图邻接矩阵$O(n)$$O(n^2)$$O(n^2)$可 $O(1)$ 判边存在仅适合稠密图邻接表$O(d^(u))$$O(nm)$$O(m)$各种图都适合应用最广链式前向星$O(d^(u))$$O(nm)$$O(m)$边带编号反向边可用i^1获取其中 $d^(u)$ 表示点 $u$ 的出度。DFS 文档中给出的 $O(nm)$ 复杂度正是在邻接表或前向星存储下才成立的若使用直接存边或邻接矩阵遍历整张图的复杂度将分别退化为 $O(nm)$ 与 $O(n^2)$。DFS 序列DFS 序列是指 DFS 调用过程中访问的节点编号的序列。它有一个对算法竞赛极为重要的性质每个子树都对应 DFS 序列中的连续一段一段区间。这是因为 DFS 一旦进入某棵子树会完整地遍历完该子树的所有节点后才回溯离开因此子树内的节点在访问序列中必然连续出现。这一性质使得子树区间可以转化为数组区间从而能用线段树、树状数组等区间数据结构维护子树信息是众多树上算法如树上启发式合并 dsu-on-tree、虚树 virtual-tree、树哈希 tree-hash 等的基础。括号序列括号序列是 DFS 序列的一种扩展记录方式DFS 进入某个节点的时候记录一个左括号(退出某个节点的时候记录一个右括号)。由此可以推出两个直观性质每个节点会出现两次进入一次记录(退出一次记录)相邻两个节点的深度相差 1序列中任意相邻的两个符号恰好跨越一次进/出操作深度变化恰好为 ±1。括号序列将树的嵌套结构显式地编码为括号串本质上与每个子树对应 DFS 序中连续区间是同一性质的两种表述。它在诸如树上括号匹配类问题、以及某些需要显式表达节点进入/退出时刻的算法中非常有用。一般图上 DFS将 DFS 放在一般不一定连通、不一定为树的图上考察有以下结论对于非连通图从单个起点出发的 DFS只能访问到起点所在的连通分量。若要遍历整张图需要对每个尚未访问的节点都重新发起一次 DFS。对于连通图DFS 序列通常不唯一——访问顺序取决于起点选择与邻接点的遍历顺序。注树的 DFS 序列也是不唯一的。在 DFS 过程中通过记录每个节点从哪个点访问而来即记录树边可以建立一个树结构称为DFS 树。DFS 树是原图的一个生成树原图的所有节点都在这棵树中树边都是原图的边。DFS 生成树有很多重要性质比如可以用来求 强连通分量。在 docs/graph/scc.md 中有向图 $G$ 的边被分为四类树边tree edge搜索中第一次访问到新节点形成的边所有树边组成 DFS 生成树返祖边back edge从某节点指向其祖先的非树边前向边forward edge从某节点指向其子树中后代节点的非树边横叉边cross edge指向非祖先、非后代且已访问节点的边。需要注意的是生成树的具体结构以及上述边分类都依赖于 DFS 的起始结点选择和邻接点的访问顺序。在 OI-wiki 竞赛算法中的典型应用源码佐证DFS 是大量图论算法的基础设施。仓库中多处源码直接体现了 DFS 的典型用法下面按利用 DFS 的哪个性质分类列举1. 树的遍历与子树信息统计递归 回溯累积DFS 是树上信息统计的天然工具进入节点时初始化、递归子节点、回溯时合并子节点信息。仓库 tree-centroid-1.cpp对应 树的重心在 DFS 中统计子树大小并计算重心void dfs(int u) { siz[u] 1, ans[u] u; for (int v : son[u]) { dfs(v); siz[u] siz[v]; // 回溯时累加子树大小 weight[u] max(weight[u], siz[v]); } // ... 根据子树大小判断重心 }2. 两次 DFS 求树的直径树的直径问题见 docs/graph/tree-diameter.md是DFS 最远点的经典应用先从任意点出发 DFS 找到最远点 $c$再从 $c$ 出发 DFS 得到的最远距离即为直径。仓库 tree-diameter_1.cpp 正是这一实现其 DFS 同时记录深度并维护最远点。3. DFS 时间戳dfn与割点/割边在 割点与割边 的 Tarjan 算法中DFS 被用来给每个节点打上访问时间戳dfn并维护数组low不经过其父亲能到达的最小时间戳进而判断割点与桥。这正是在基础 DFS 结构上加入代码利用 DFS 性质的典型例子——判断割点的核心条件是对某顶点 $u$若存在其儿子 $v$ 使得 $low_v \geq dfn_u$则 $u$ 为割点。仓库实现见 cut_1.cpp。4. DFS 生成树与强连通分量上文提到的 DFS 生成树四类边分类直接支撑了 Tarjan 算法求强连通分量每个强连通分量对应搜索树中的一棵子树算法在 DFS 过程中维护dfn与low每当dfn[u] low[u]时弹出栈中节点构成一个 SCC。这也印证了 DFS 文档中DFS 树可以用来求强连通分量的结论。5. 利用 DFS 序将子树问题转化为区间问题LCA 倍增/Tarjan 算法docs/graph/lca.md均需先 DFS 预处理深度、祖先信息或时间戳仓库代码见 lca_1.cpp树上启发式合并dsu on treedocs/graph/dsu-on-tree.md需要先用 DFS 预处理每个节点的子树大小与重儿子再按轻儿子/重儿子顺序遍历其正确性正依赖于 DFS 序的区间连续性。这些应用说明掌握 DFS 的本质递归调用 访问标记 在递归前后插入逻辑就能自然理解 OI 中大量看似高级的树上与图上算法。常见误区小结把图论 DFS 与搜索 DFS 混为一谈图论 DFS 是遍历算法DFS搜索 指用递归函数实现暴力枚举的思想两者定义不同、用途不同。出栈/入栈时机混淆显式栈实现必须入栈时打标记否则栈中会出现重复元素。忽视栈空间递归 DFS 深度最坏为 $O(n)$本地调试需按前文方式调整栈限制而评测环境NOIP、省选、CCF 赛事普遍支持无限栈空间但总内存仍受题面限制。存储方式影响复杂度$O(nm)$ 的复杂度只在邻接表/前向星存储下成立邻接矩阵与直接存边会退化为 $O(n^2)$ 与 $O(nm)$。延伸阅读图的存储方式邻接表、链式前向星、邻接矩阵docs/graph/save.mdBFS广度优先搜索与 DFS 对比学习docs/graph/bfs.mdDFS 生成树与强连通分量Tarjan 算法docs/graph/scc.md基于 DFS 时间戳的割点与割边docs/graph/cut.md递归搜索思想与例题docs/search/dfs.md栈与队列容器docs/ds/stack.md、docs/ds/queue.md【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考