有向图上的 DFS 与边分类

有向图中，同一个 DFS 框架会产生四类边。分类反映两个端点在深度优先森林中的关系，也是判环、拓扑排序和强连通分量的基础。

1. 四类边

遍历边 $(u,v)$ 时：

• 树边：$v$ 是白色，边使 $v$ 第一次被发现；
• 后向边：$v$ 是灰色，边从当前结点指向递归栈中的祖先；
• 前向边：$v$ 已是黑色，且是 $u$ 的后代，但这条边不是树边；
• 横向边：$v$ 已是黑色，且与 $u$ 没有祖先后代关系。

白、灰、黑足以在线区分树边和后向边；区分前向与横向可使用时间戳。

2. 时间戳判定

对边 $(u,v)$：

• 树边或前向边满足

$$d[u]<d[v]<f[v]<f[u];$$

• 后向边满足

$$d[v]<d[u]<f[u]<f[v];$$

• 横向边的两个时间区间互不相交。

树边与前向边都有包含关系，要结合 parent[v] == u 才能区分。

3. 为什么有向图会出现横向边

从一个分支完全搜索结束后，另一个分支可能有边指向前一个已经变黑的顶点；方向阻止搜索从前一分支走回当前分支，所以二者不是祖先后代。这在有向图中完全正常。

无向图不会出现真正的前向边和横向边：如果两个顶点之间有无向边，先被探索的一侧本应沿该边发现另一侧，除非那条关系已经是树边或祖先后代间的后向边。

4. 有向图判环

有向图存在环，当且仅当 DFS 过程中出现后向边。

• 后向边 $(u,v)$ 加上 DFS 树中从祖先 $v$ 到后代 $u$ 的路径，直接组成有向环；
• 若图有环，取环上最先被发现的顶点 $v$。在它完成之前，DFS 会沿环探索，最终遇到一条指回仍为灰色的 $v$ 或其祖先的边。

因此三色 DFS 中，遇到灰色邻居就能立即报告有环。

5. 为什么“访问过”一个布尔值不够

仅有 visited 无法区分：

• 邻居仍在当前递归路径上，说明形成后向边；
• 邻居早已完成，只是前向边或横向边，并不必然有环。

所以有向图判环必须维护递归栈状态，三色法正是最清楚的表达。

6. 递归栈的等价实现

也可以维护 visited[v] 与 inStack[v]：进入时二者设真，退出时清除 inStack。发现指向 inStack 顶点的边即有环。三色法中灰色就等价于 inStack=true。

7. DFS 顺序不是唯一的

邻接顺序改变时，某条边可能在一次 DFS 中是树边，在另一次中是前向或横向边。唯一稳定的结构结论是：只要图有环，任何完整 DFS 都会出现后向边；若没有后向边，图就是 DAG。

8. 为后续算法保存什么

• 判环只需颜色；
• 拓扑排序需要完成顺序；
• 强连通分量需要第一遍 DFS 的完成时间排序；
• 恢复具体环还要保存父指针，在发现后向边时沿父指针回溯。

先明确目标，再决定是否需要保存全部时间戳，避免无意义的数据结构。