为了找那种图形的边缘，在此我们采用了深度优先搜索算法，我们可以使用这样的：

In order to find the kind of the edges of a graph, at which we applied the Depth-first search algorithm, we could use this:

树边：X - >Ÿ当[D [Y]，F [Y]]⊂[D [X]，F [X]]

tree edges: x -> y when [d[y],f[y]] ⊂ [d[x],f[x]]

前边缘：X - >Ÿ当[D [X]，F [X]]⊂[D [Y]，F [Y]]

forward edges: x -> y when [d[x],f[x]] ⊂ [d[y],f[y]]

回边缘：X - >Ÿ当[D [Y]，F [Y]]⊂[D [X]，F [X]]

back edges: x -> y when [d[y],f[y]] ⊂ [d[x],f[x]]

交叉边缘：X - >Ÿ当[D [X]，F [X]]∩[D [Y]，F [Y]] =∅

Cross edges: x -> y when [d[x],f[x]] ∩ [d[y],f[y]]=∅

发现时间的：发现时间d [V]是发现或完成之前先看到的节点的个数v

Discovery Time: The discovery time d[v] is the number of nodes discovered or finished before first seeing v.

精加工时间的：该精加工时间t [V]是发现或成品精$ V $的膨胀前的节点数目

Finishing Time: The finishing time f[v] is the number of nodes discovered or finished before finishing the expansion of $v$.

这是我在看的图：

和这里的发现和结束时间，我发现：

And here are the discovery and finish times I found:

算法：

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]]怎么才能知道它是树的边缘或后缘？

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 back 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? If so, could you explain me why?

此外，不JH，IA前边缘和股份公司后边缘？还是我错了？

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

推荐答案

您关系的前进和后退边是不正确的 - 你应该换的。 除此之外，我建议你阅读这一段从维基百科： 的http://en.wikipedia.org/wiki/Depth-first_search#Output_of_a_depth-first_search 它包括那些边缘和良好的画面更直观，更直接的定义：

Your relationships for forward and back edges are incorrect - you should exchange them. Apart from that, I would recommend reading this paragraph from wikipedia: http://en.wikipedia.org/wiki/Depth-first_search#Output_of_a_depth-first_search it includes a more intuitive and straightforward definition of those edges and a good picture:

当我们的情况为例[D [Y]，F [Y]]⊂[D [X]，F [X]]怎能   知道这是树的边缘或转发的边缘？

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?

如果边缘所属的树 - 这是树的边缘（和所有的树边符合上述的关系）。 如果边缘不属于树和它满足上面的关系 - 这是一个前沿

If an edge belongs to the tree - it is a tree edge (and all tree edges fulfill the relationship above). If an edge doesn't belong to the tree and it fulfills the relationship above - it is 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?

是的，但我们需要记住，树边是蓝色和红色边的树只是一个再presentation，他们在另一个方向指向。所以，如果有一个红色箭头 X - ＆GT;是，这意味着一个蓝色箭头Ÿ - ＆GT; X 属于树（也可能是显而易见的你）。您也可以阅读生成树的定义： http://en.wikipedia.org/wiki/Spanning_tree#Definitions

Yes, however we need to remember that tree edges are blue and red edges are just a representation of the tree and they point in the other direction. So, if there is a red arrow x -> y, it means that a blue arrow y -> x belongs to the tree (it may be obvious for you). You may also read the definition of the spanning tree: http://en.wikipedia.org/wiki/Spanning_tree#Definitions

此外，不JH，IA前边缘和股份公司后边缘？还是我错了？

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

这正是周围的其他方法：JH，IA回来边缘，AG是一个前沿（因为你的前进和后退边的关系是不正确的）

It's exactly the other way around: jh,ia are back edges and ag is a forward edge (because your relationships for back and forward edges are incorrect).

当您在图表上运行的DFS，它通过设置 P [V] = U 在访问（U）（这意味着顶点 U 是顶点的父 v 输入图中的生成树）。

When you run DFS on a graph, it produces a representation of a spanning tree of this graph by setting p[v]=u in Visit(u) (which means that vertex u is a parent of vertex v in the spanning tree of the input graph).

您已经绘制正确使用红色箭头这种重presentation。然而，实际上形成一个图形的生成树是该曲线图（或它们的子集为precise）的边缘。因此，要知道，如果一个蓝色 X - ＆GT;图的是边属于该图的生成树，我们需要检查是否有Ÿ - ＆GT; X 红边在您的图片，或者换句话说，如果 X 是 y的父（ P [Y] == X ）的生成树。

You have correctly drawn this representation using red arrows. However, what actually forms the spanning tree of a graph are the edges of this graph (or a subset of them to be precise). So, to know if a blue x -> y edge of the graph belongs to the spanning tree of this graph, we need to check if there is an y -> x red edge in your picture or, in other words, if x is a parent of y (p[y] == x) in the spanning tree.

让我们来看看为什么 JH 是一个底部。我们需要看你的第二个画面：

Let's find out why jh is a back edge. We need to look at your second picture:

在DFS开始在 A 。之后已访问顶点 C，F，G 它回溯到 A 来访 D 首次（它增加了边缘的 - > d可生成树的DFS正在建设）。然后，它访问 2H，J ，现在它要访问 ^ h ，但它已经被访问和 ^ h 有一个较小的发现时间比Ĵ，所以我们搬回 - 这是一个后缘

The DFS starts in a. After it has visited vertexes c,f,g it backtraces to a and visits d for the first time (which adds edge a -> d to the spanning tree the DFS is building). Then, it visits h,j and now it wants to visit h but it's already been visited and h has a smaller discovery time than j, so we are moving back - it is a back edge.