DFS中的边缘分类

Question

根据书(算法简介),在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是后边缘)
• if entry(u)>entry(current),那么你是当前顶点的后代(current-> u是前沿)
• 否则,它是一个交叉边缘

请注意,这些关系用于在算法运行期间进行检查.算法完成后,基本上检查祖先

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