DFS中的边缘分类 [英] Edge classification in a DFS

问题描述

根据这本书（算法简介），在dfs中，边缘分为4种：

According to the book (Intro to Algorithm), in dfs, edges are classified as 4 kinds:

1. 树边缘（如果存在）边缘（u，v），首先发现v，然后（u，v）是
   a树边缘。


2. 后边缘，如果......，v是


3. 前缘，如果......，则表明v已被发现并且v是u的后代，即前缘


4. 交叉边缘，除上述三个以外的所有边缘。

1. Tree Edge, if in edge (u,v), v is first discovered, then (u, v) is a tree edge.
2. Back Edge, if ......, v is discovered already and v is an ancestor, then it's a back edge.
3. Forward Edge, if ......, v is discovered already and v is a descendant of u, forward edge it is.
4. Cross Edge, all edges except for the above three.

我的问题试图确定（u，v）是后边缘还是前边缘时，如何确定v是您的祖先还是后代？

My question is how can I identify whether v is u's ancestor or descendant when I'm trying to figure out if (u, v) is a back or forward edge?

推荐答案

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

If you really need it, you can check it by maintaining so called entry and exit times for each node. During the run of the algorithm, you increment a time variable (starting from 0, of course) each time you encounter a new vertex. The times entry_t(v), exit_t(v) are initially unset for all vertices.

第一次遇到顶点时，设置 entry（v）：= time 。当您通过上升沿退出顶点（即，从堆栈中弹出顶点）时，可以设置其 exit（v）：= time 。这样，您可以

When you first encounter a vertex, you set entry(v):=time. When you exit a vertex by an up edge (ie. poping the vertex from the stack), you set its exit(v):=time. With that, you have

• 如果设置了 entry（u）且 exit（u）未设置，则u是当前顶点的祖先（即vu是后边缘）


• 如果 entry（u）> entry（current），则u是当前顶点的后代（current-> u是前缘）


• 否则，这是一个交叉边缘

• if entry(u) is set and exit(u) is not set, then u is ancestor of the current vertex (ie. vu is a back edge)
• if entry(u)>entry(current), then u is descendant from the current vertex (current->u is a forward edge)
• otherwise, it is a cross edge

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

Note that these relations are made for checking during the run of the algorithm. After the algorithm has completed, a check of ancestry is basically

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

这篇关于DFS中的边缘分类的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！