深度优先搜索

DFS 把“稍后继续处理的分支”留在栈帧中，先把当前分支走到底。一个帧不仅保存顶点，还保存下一条待扫描的邻接记录。递归进入白色邻点时，父帧暂停；子调用结束后，父帧从原位置继续。只有最后一条邻接记录也处理完，当前顶点才变黑并出栈。

这说明区间为什么只能嵌套或分离：发现另一个顶点时，若旧调用尚未结束，新调用必须在它返回之前结束；若旧调用已经返回，两段时间便不会重叠。邻接次序会改变树、时间戳和输出顺序，却不会改变从给定源可达的顶点集合。

这里不能把“用栈遍历”直接等同于标准 DFS。若一次性把当前点的所有邻点压栈并立即标记，就可能把本应先从某个孩子深入发现的顶点提前登记为兄弟，破坏上述祖先与时间区间的解释。要保留这些性质，显式栈应像图中的调用帧一样，每次只推进一个尚未处理的邻接项。

与按层推进的广度优先搜索理路广度优先搜索Breadth-first search · BFS按无权距离分层访问可达顶点的图遍历算法。相比，DFS 没有距离单调性。它换来的信息是活动路径和退出顺序：灰色顶点恰是当前递归祖先，遇到指向灰色祖先的边便得到了一个有向圈证据。

在有向图

中，若 $1$ 的邻接表先列 $2$，并让发现与完成共用从 $1$ 递增的计时器，依次得到 $d[1]=1,d[2]=2,d[4]=3$。扫描 $4\to 2$ 时 $2$ 仍为灰色，这条回边与树路 $2⇝4$ 合成有向圈。随后 $4$、$2$ 完成，时间分别为 $4,5$；回到 $1$ 才发现 $3$，得到 $d[3]=6,f[3]=7,f[1]=8$。

按顶点 $1,2,4,3$ 的发现顺序，区间分别是 $[1,8],[2,5],[3,4],[6,7]$：$2$ 与 $3$ 的区间分离，$4$ 的区间包含在 $2$ 内。扫描 $3\to 4$ 时 $4$ 已为黑色；仅凭“目标已访问”会把一条跨向已完成分支的边误报成回边。这条轨迹也说明必须在扫描邻点前标灰，否则环会使递归反复进入同一个节点。

有向图中，指向白点的是树边，指向灰色祖先（包括自身）的边是回边；自环因而直接给出长度一的有向圈。指向黑点的边要结合时间区间区分前向边与交叉边。有向图无环当且仅当任意完整 DFS 森林都没有回边。无向图的非树边只连接祖先与后代，但扫描父边的反向记录不构成圈；若允许平行边，必须按边 ID 排除那一条父边，因为另一条平行边确实形成长度为二的多重图圈。

DFS 首次找到的路径一般不是最短路：在边 $s\to a,a\to t,s\to t$ 中，若先深入 $a$，得到两条边的树路，尽管直达边只需一步。递归实现还可能在长度为 $n-1$ 的链上耗尽语言运行时栈；显式栈能控制存储位置，但仍需 $\mathrm{\Theta }(n)$ 最坏空间。若要精确复现递归版的完成时间，栈帧必须同时保存“邻接表已经扫描到哪里”，而不能只压入顶点编号。

确认有向图无回边后，逆完成序可构造拓扑排序理路拓扑排序Topological sort给有向无环图顶点排列线性次序，使每条边从前指向后。，两次 DFS 可分解强连通分量理路强连通分量算法Strongly connected components algorithm在线性时间内把有向图划分为互相可达的极大顶点集合。，发现时间与Low-link 值理路Low-link 值Low-link value · LowlinkDFS 子树通过树边和受允许的非树边能够到达的最早发现时间摘要。可识别桥、割点和分量。它们共享遍历骨架，正确性却分别依赖“无回边”“凝聚图次序”或“子树能回到多早”的附加不变量。

发现/完成区间还把 DFS 树的子树映成嵌套区间，树的 Euler Tour 技巧理路树的 Euler Tour 技巧Euler tour technique for trees用 DFS 次序把子树或树上行走线性化，并区分三种常见序列。据此支持祖先或子树查询。一般有向图的非树边不会因此消失；只有先明确要查询的是 DFS 森林结构，才能把区间结论用于原图问题。

在单入口 flow graph 中，Lengauer–Tarjan 算法理路支配树与 Lengauer–Tarjan 算法Dominator tree · Lengauer–Tarjan algorithm · 支配树从全部入口路径定义支配关系，用可手算例子解释半支配点、路径最小值、延迟判定与 LT 算法的两种复杂度界。借 DFS 编号组织半支配点，但 DFS parent 只代表首次到达，未必支配子节点。边一旦插删，原有搜索树、时间区间和边分类都可能改变；本页的线性界只描述一次静态遍历，不是动态图维护保证。