algorithm - 图的边

Question

为了找到我们应用深度优先搜索算法的图形边的种类，我们可以使用这个:

树边:x -> y 当 [d[y],f[y]] ⊂ [d[x],f[x]]

前向边缘:x -> y 当 [d[x],f[x]] ⊂ [d[y],f[y]]

后边:x -> y when [d[y],f[y]] ⊂ [d[x],f[x]]

交叉边:x -> y 当 [d[x],f[x]] ∩ [d[y],f[y]]=∅

发现时间:发现时间 d[v] 是在第一次看到 v 之前发现或完成的节点数。

Finishing Time:完成时间 f[v] 是在完成 $v$ 扩展之前发现或完成的节点数。

这就是我正在查看的图表:

这是我找到的发现时间和完成时间:

算法:

Depthfirstsearch(G)
   for each v ∈ V
        color[v]=white
        p[v]=NIL
   time=0
   for each v ∈ V
       if color[v]=white then
          Visit(v)


Visit(u)
  color[u]=gray
  time=time+1
  d[u]=time
  for each v ∈ Adj[u]
       if color[v]=white then
          p[v]=u
          Visit(v)
  color[u]=black
  time=time+1
  f[u]=time

例如，当我们遇到 [d[y],f[y]] ⊂ [d[x],f[x]] 的情况时，我们如何知道它是树边还是后边？

我们是否必须像那样标记每个节点的父节点:

如果有红边我们就知道是树边？如果是这样，你能解释一下为什么吗？

此外，jh,ia 不是前向边缘，ag 不是后向边缘吗？还是我错了？

Answer 1

您的前向和后向边缘关系不正确 - 您应该交换它们。
除此之外，我建议阅读维基百科的这段话:
http://en.wikipedia.org/wiki/Depth-first_search#Output_of_a_depth-first_search
它包括对这些边缘的更直观和直接的定义以及一张好图:

直接回答您的问题

When we have for example the case [d[y],f[y]] ⊂ [d[x],f[x]] how can we know if it is a tree edge or a forward edge?

如果一条边属于树——它就是树边(并且所有树边都满足上面的关系)。
如果边不属于树并且它满足上述关系 - 它是前向边。

Do we have to mark the parent of each node, like that: [...] and if there is red edge we know that it is a tree edge?

是的，但是我们需要记住，树的边缘是蓝色的，红色的边缘只是树的代表，它们指向另一个方向。因此，如果有一个红色箭头 x -> y，则意味着蓝色箭头 y -> x 属于这棵树(这对你来说可能很明显)。您还可以阅读生成树的定义:
http://en.wikipedia.org/wiki/Spanning_tree#Definitions

Also, aren't jh,ia forward edges and ag a back edge? Or am I wrong?

正好相反:jh,ia 是后边，ag 是前边(因为后边和前边的关系不正确)。

更长的解释

当您在图上运行 DFS 时，它会通过在 Visit(u) 中设置 p[v]=u 来生成该图的生成树表示(这意味着顶点 u 是输入图生成树中顶点 v 的父节点。

您已使用红色箭头正确绘制此表示。然而，真正构成图的生成树的是这个图的边(或者准确地说是它们的子集)。因此，要知道图中的蓝色 x -> y 边是否属于该图的生成树，我们需要检查是否存在 y -> x图片中的红色边缘，或者换句话说，如果 x 是 y (p[y] == x) 的父级生成树。

让我们找出为什么 jh 是后边。我们需要看看你的第二张照片:

DFS 从 a 开始。在它访问了顶点 c,f,g 之后，它回溯到 a 并第一次访问 d(添加边 a -> d到 DFS 正在构建的生成树)。然后，它访问 h,j 现在它想访问 h 但它已经被访问过并且 h 的发现时间比 >j，所以我们向后移动 - 这是一个后缘。