Edges of the graph

Question

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:

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

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

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

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

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

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

That's the graph I am looking at:

enter image description here

And here are the discovery and finish times I found:

enter image description here

Algorithm:

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

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:

enter image description here

and if there is red edge we know that it is a tree edge? If so, could you explain me why?

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

MD-11 MD-11 · Accepted Answer · 2014-12-15T16:14:22

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: enter image description here

Direct answers to your questions

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?

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

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

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).

Longer explanation

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).

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.

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

DFS

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.

Edges of the graph

1 Answers

Direct answers to your questions

Longer explanation