文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载深度优先搜索Depth First SearchDFS是 cp-algorithms 仓库中图论算法家族的基石几乎所有重要的图算法拓扑排序、桥、割点、强连通分量、LCA 等都以它为内核。本文以 src/graph/depth-first-search.md 为骨架结合仓库中src/graph/目录下的相关实现与test/目录下的测试用例系统讲解 DFS 的原理、两种 C 实现、有向图边的分类定理以及基于 DFS 构建的六大经典应用读完后你能够独立用 DFS 解决祖先判断、拓扑排序、环检测、桥与割点、强连通分量等竞赛高频问题。DFS 的核心思想与复杂度DFS 的思路非常直白尽可能深入地沿着图的边向前走直到抵达一个所有相邻顶点都被访问过的顶点再回溯。具体来说从某个起始顶点开始搜索访问一个顶点后依次对它的每个尚未访问过的相邻顶点递归地执行 DFS这样就能访问到从起始顶点可达的全部顶点。这种一路走到底再回头的特性使它区别于广度优先搜索BFSDFS 能找出从源点 $u$ 到每个顶点的字典序最小路径按邻接表顺序遍历时第一条被找到的路径即为字典序最小者在树中 DFS 找到的就是最短路径因为树中任意两点之间只有一条简单路径但在一般图上 DFS 找到的路径不一定是最短路径算法的总时间复杂度为$O(m n)$其中 $n$ 是顶点数、$m$ 是边数每个顶点被访问一次每条边在递归过程中至多被处理一次。基础实现递归版 DFS仓库原文档给出的最简实现采用邻接表存储图vectorvectorint adj; // graph represented as an adjacency list int n; // number of vertices vectorbool visited; void dfs(int v) { visited[v] true; for (int u : adj[v]) { if (!visited[u]) dfs(u); } }这段代码只有两个关键动作进入顶点时标记visited[v] true对所有未访问的邻居递归调用dfs。它足以完成连通分量统计、可达性判断等基础任务。进阶实现三色标记与 entry/exit 时间戳基础版本只能区分访问过 / 未访问过但 DFS 的许多进阶应用祖先判断、拓扑排序、桥、割点还需要知道每个顶点何时进入、何时退出。原文档因此给出了一种通用的三色实现颜色 0未访问颜色 1已访问但尚未退出颜色 2已访问且已退出。vectorvectorint adj; // graph represented as an adjacency list int n; // number of vertices vectorint color; vectorint time_in, time_out; int dfs_timer 0; void dfs(int v) { time_in[v] dfs_timer; color[v] 1; for (int u : adj[v]) if (color[u] 0) dfs(u); color[v] 2; time_out[v] dfs_timer; }这里的time_inentry time与time_outexit time是后续一切进阶应用的关键原材料顶点 $v$ 的 DFS 调用尚未返回时$v$ 处于颜色 1正在访问中状态一旦 $v$ 的递归调用返回$v$ 处于颜色 2同时记录下time_out[v]计时器dfs_timer在整个搜索过程中单调递增天然编码了 DFS 调用栈的进入—退出顺序。这套时间戳 三色的模式在整个仓库中反复出现比如 桥查找的实现 和 割点查找的实现 中tin/low数组的语义就是从time_in演化而来强连通分量Tarjan 算法 中的t_in/t_low同样遵循这套时间戳体系。有向图的边分类利用顶点 $u$、$v$ 的 entry/exit 时间可以将 DFS 过程中遇到的每条边 $(u, v)$ 分为四类。这套分类是桥bridge与割点articulation point问题的基础。前提假设我们按照 DFS 遍历到边的顺序来分类。树边Tree Edge如果顶点 $v$ 是在访问 $u$ 的过程中第一次被发现即 $v$ 尚未被访问、$u$ 正处于访问中则 $(u, v)$ 称为树边。所有树边构成一棵DFS 树这也是树边名称的由来。树边是 DFS 树上的父子关系边。回边Back Edge如果 $v$ 是 $u$ 的祖先——即我们已经进入过 $v$ 但还没有退出 $v$——那么 $(u, v)$ 是回边。回边从后代 $u$ 指向祖先 $v$而 DFS 递归过程中本已存在一条从祖先 $v$ 到后代 $u$ 的路径二者拼接即形成一个环。环cycle正是通过回边被检测出来的一个图无环当且仅当 DFS 过程中不出现任何回边。前向边Forward Edge如果 $v$ 是 $u$ 的后代即已经访问并退出 $v$且 $\text{entry}[u] \text{entry}[v]$则 $(u, v)$ 是前向边。前向边本质上是指向子树的边。交叉边Cross Edge如果 $v$ 既不是 $u$ 的祖先也不是 $u$ 的后代即已经访问并退出 $v$且 $\text{entry}[u] \text{entry}[v]$则 $(u, v)$ 是交叉边。交叉边横跨两棵不同的 DFS 子树。关键定理无向图只有树边与回边定理设 $G$ 是无向图在 $G$ 上执行 DFS所有遇到的边要么是树边、要么是回边前向边和交叉边只存在于有向图中。原文档给出了完整证明其核心论证如下。任取无向边 $(u,v)$不失一般性设 $u$ 先于 $v$ 被访问$\text{entry}[u] \text{entry}[v]$而 DFS 每条边只处理一次因此只有两种处理方式第一次探索 $(u,v)$ 是从 $u$ 到 $v$ 方向。由于 $\text{entry}[u] \text{entry}[v]$ 且 DFS 是递归的$v$ 一定会在我们回溯退出 $u$之前被完整探索并退出。此时 $v$ 必然是未访问的——否则边早已被 $v$ 向 $u$ 的方向探索过了。因此 $(u,v)$ 是树边。第一次探索 $(u,v)$ 是从 $v$ 到 $u$ 方向。既然 $u$ 先被发现而边只处理一次$v$ 能沿这条边走到 $u$ 的唯一可能是存在一条不经过 $(u,v)$ 的、从 $u$ 到 $v$ 的路径从而 $u$ 成为 $v$ 的祖先。于是 $(u,v)$ 从后代 $v$ 指向尚未退出的祖先 $u$补全了一个环是回边。两种情况已穷尽所有可能定理得证。基于 DFS 的六大经典应用1. 任意路径查找与字典序第一路径由于 DFS 从源点 $u$ 出发会系统地访问所有可达顶点因此可以直接回答从 $u$ 到 $v$ 是否存在路径当邻接表按字典序组织邻居时DFS 首次抵达 $v$ 时走过的路径就是字典序最小路径。这也是竞赛中迷宫可达性连通性判断类问题例如原文档练习列表中的 SPOJ ABCPATH、MAKEMAZE 等的通用解法。2. $O(1)$ 祖先判断entry/exit 时间戳利用进阶实现记录的time_in/time_out可以在 $O(1)$ 内回答顶点 $i$ 是否为顶点 $j$ 的祖先顶点 $i$ 是顶点 $j$ 的祖先当且仅当 $\text{entry}[i] \text{entry}[j]$且$\text{exit}[i] \text{exit}[j]$。直觉祖先的 DFS 调用一定先于后代进入、后于后代退出所以祖先的进入—退出时间区间完整包裹住后代的区间。这一判定是 LCA、树剖HLD等算法判断节点相对位置的底层工具。3. 最近公共祖先LCA原文档列出的 LCA 应用在仓库中有专门文章 src/graph/lca.md。其思想是对树做一次 DFS 得到Euler 序列每次首次访问某顶点以及从每个孩子子树返回时都记一次该顶点配合每个顶点首次出现的位置first[i]LCA 查询被归约为 Euler 序列区间上的RMQ区间最小值问题——区间内高度最小的顶点即答案。用 Sqrt 分解可在 $O(N)$ 预处理、$O(\sqrt N)$ 单次查询用线段树线段树文章可在 $O(N)$ 预处理、$O(\log N)$ 查询因为几乎没有更新操作用 Sparse Table 可将查询优化到 $O(1)$预处理 $O(N \log N)$。仓库中src/graph/lca.md提供了以线段树实现的完整struct LCA代码其dfs递归过程正是进入时记录、返回后再次记录的标准 Euler 遍历。4. 拓扑排序按退出时间降序对 DAG 执行一系列 DFS保证每个顶点恰好被访问一次复杂度 $O(n m)$。拓扑序恰好是各顶点按退出时间exit time降序排列的结果。原因很直观设存在边 $v \to u$则 $u$ 在dfs(v)内部被访问因此 $u$ 的退出时间必然早于 $v$ 的退出时间退出时间晚的顶点在拓扑序中应排在前面。仓库的 src/graph/topological-sort.md 给出了完整实现DFS 返回前把顶点压入ans结束后reverse(ans)即为拓扑序。该文还指出即使图有环这个实现仍保留若 $v$ 可达 $u$ 则 $v$ 先于 $u$ 输出的偏序性质这一性质被 Kosaraju 强连通分量算法 直接利用。5. 环检测统计回边因为回边是且仅是环的产物所以判断图是否无环等价于判断 DFS 过程中是否出现回边——在每个连通分量内分别统计回边数量即可。这在仓库的 拓扑排序文章 中被明确提及若需要可以按 DFS 文章所述检测图是否有环以决定拓扑序是否存在。6. 有向图强连通分量Kosaraju 算法的两步都基于 DFS其流程在原文档及仓库的 强连通分量文章 中均有阐述第一趟 DFS按任意顺序遍历全图按退出时间递增的顺序收集顶点得到顶点列表order转置图 第二趟 DFS构造转置图 $G^T$按order的逆序即退出时间降序再次 DFS每次 DFS 调用覆盖的顶点集恰好是一个强连通分量可选构建缩点图condensation graph。正确性依赖于两个定理缩点图上每条边都从退出时间较大的分量指向较小的分量以及 $G$ 与转置图 $G^T$ 具有相同的强连通分量集。仓库 强连通分量文章 还给出了Tarjan 算法的完整实现基于t_in/t_low时间戳与一个保存未认领顶点的栈并在文末注明其在 Library Checker 上通过了评测提交。7. 无向图的桥与割点虽然原文档只列出寻找桥的应用点但仓库将其扩展为两篇独立文章桥bridgesrc/graph/bridge-searching.md。DFS 树边 $(v, to)$ 是桥当且仅当low[to] tin[v]其中low[v]定义为从 $v$ 或其后代出发、通过一条回边或树边能到达的最小tin。实现需要传入父顶点参数p并用parent_skipped标志处理重边情形。仓库测试 test/test_bridge_searching_offline.cpp 用三个用例验证了该实现其中第一个用例特意构造了0-1两条重边断言重边不算桥。割点articulation pointsrc/graph/cutpoints.md。非根顶点 $v$ 是割点当且仅当存在 DFS 树孩子to满足low[to] tin[v]根顶点则是割点当且仅当它在 DFS 树中有多于一个孩子。原文档给出的桥查找思路先把无向图定向化再找强连通分量跨分量的边即桥是从 SCC 出发的等价视角与上述low/tin的经典做法互补。仓库源码与测试印证本仓库并非只有文档——test/目录为多个 DFS 衍生算法提供了可运行的 C 测试验证了文档实现的正确性test/test_bridge_searching_offline.cpp包含三组针对桥查找算法的用例重边、环、多条链断言输出桥集合与期望完全一致test/test_strongly_connected_components.cpp在 10 顶点图上运行strongly_connected_components断言得到的 4 个分量恰为{0,7}、{1,2,3,5,6}、{4,9}、{8}并校验了缩点图的边集test/test_tarjan_scc.cpp对应 Tarjan 版强连通分量实现test/test_lca.cpp覆盖 Euler 序列 线段树的 LCA 查询。test/test.sh将这些用例统一编排运行你可以在本地按 README.md 说明克隆仓库后用test/clean.sh、test/test.sh复现。这些测试证明了文档中给出的 DFS 相关实现不仅是教学示例而且是经过断言验证、可放心移植进竞赛代码的可靠实现。复杂度与适用性小结问题实现手段复杂度可达性 / 路径查找基础 DFS$O(n m)$祖先判断time_in/time_out区间$O(1)$ 每次拓扑排序DFS 退出时间降序$O(n m)$环检测统计回边$O(n m)$桥 / 割点tin/low$O(n m)$强连通分量Kosaraju / Tarjan各两趟 DFS$O(n m)$LCAEuler 序列 RMQ预处理 $O(N)/O(N\log N)$查询 $O(1)/O(\log N)$需要注意的边界与限制DFS 找到的路径在一般图上不保证最短只有树中才是唯一路径边分类中的前向边、交叉边仅在有向图中存在重边、自环等细节在具体实现如桥查找中需要专门处理。练习建议原文档末尾给出了大量按平台组织的练习题涵盖 DFS 可达性、迷宫遍历、树上 DFS、拓扑序、割点与桥、SCC 等题型。其中包括SPOJ 系列ABCPATH字母路径、EAGLE1、ADASEA、KOZE绵羊、MAKEMAZE迷宫验证、GHOSTS、CAC仙人掌、AMR10J混合化学品等Timus 系列Werewolf、Penguin Avia、Two TeamsUVA657 The die is castCodeforces 系列Kefa and Park、Underground Lab、Anton and Tree、Centroids、The tag Game、Wizards Tour、Ring Road、Mail Stamps、Ant on the Tree 等。建议按基础 DFS → 时间戳 → 拓扑排序与环检测 → 桥/割点 → SCC → LCA的路径循序渐进每个阶段配合本仓库对应文章的实现与测试用例自行编写并验证。整体而言吃透 DFS 这一篇就等于打开了仓库中图论算法半边天的大门。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐深度优先搜索(DFS)算法图遍历的终极指南与实战解析深度优先搜索 DFS 算法图遍历的终极指南与实战解析 深度优先搜索DFS是一种强大的图遍历算法广泛应用于路径查找、拓扑排序和连通性分析等场景。GitHu示例工程教程图遍历算法对比深度优先搜索与广度优先搜索在C-Sharp-Algorithms中的实现图遍历算法对比深度优先搜索与广度优先搜索在C Sharp Algorithms中的实现 图遍历算法是计算机科学中处理图结构数据的基础技术深度优先搜索DFS后端OI-wiki 深度优先搜索DFS详解图遍历、递归与栈实现及竞赛应用OI wiki 深度优先搜索DFS详解图遍历、递归与栈实现及竞赛应用 导读 深度优先搜索Depth First SearchDFS是图论与算法竞赛中文档知识库教育教程上一篇Kilo 上游合并审查实战用七份专项报告守住 OpenCode 合并质量下一篇Haystack CacheChecker 组件详解基于 Document Store 的文档缓存命中检查创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考