graph-theory - DFS 中的边分类

Question

根据书（Intro to Algorithm），在dfs中，边缘分为4种：

1. 树边，如果在边(u,v)中，首先发现v，那么(u,v)就是树边。
2. Back Edge，如果......，v已经被发现并且v是一个祖先，那么它就是一个后边缘。
3. 前缘，如果……，v 已经被发现并且v 是u 的后代，它就是前缘。
4. Cross Edge，除上述三个外的所有边。

我的问题是当我试图确定 (u, v) 是后边还是前边时，如何确定 v 是你的祖先还是后代？

Answer 1

如果你真的需要它，你可以通过维护每个节点的所谓进入和退出时间来检查它。在算法运行期间，time每次遇到新顶点时都会增加一个变量（当然是从 0 开始）。时间entry_t(v)，exit_t(v)最初未为所有顶点设置。

当你第一次遇到一个顶点时，你设置entry(v):=time. 当您通过向上边缘退出顶点时（即从堆栈中弹出顶点），您将其设置为exit(v):=time. 有了这个，你有

• 如果entry(u)已设置exit(u)且未设置，则 u 是当前顶点的祖先（即 vu 是后边）
• 如果entry(u)>entry(current)，则 u 是当前顶点的后代（current->u 是前向边）
• 否则，它是一个交叉边缘

请注意，这些关系用于在算法运行期间进行检查。算法完成后，基本上是对祖先的检查

u is_descendant_of v = entry(u)>entry(v) and exit(u)<=exit(v)