Difference between Tree Edges and Forward Edges

Question

I was reading a book when I came across this question: How can you tell the difference between Forward Edges and Tree Edges from the Discovery and Finish Time of that specific vertex in a graph when DFS is run on it?

What I've attempted so far is that: The main difference between Fwd. and Tree Edges is that if there exists a tree edge between A and B then A is a direct neighbor of B having a path length of 1, but if's Fwd. edge, then the path length should be greater than 1 or so. So, when analyzing discovery and finish time, which could be stored in an array, we can check if their finish/start time differ by 1. Because if they do, then it's a tree edge, otherwise a forward edge.

But, I'm unable to develop an algorithm and also doubt that this approach is a buggy one. Please, help me out. Thank you.

Answer 1

While doing a depth first search on a directed graph,

1. If a visit a new node v (v has not been discovered before) from u
   than (u,v) is a tree edge.

2. else if we visit a node v already visited earlier

   • If we have not yet departed/finished from that node(v), than surely v is an ancestor of u and (u,v) a back edge.

   • Else, there are two possibilities - cross edge or forward edge. In both these cases we visit a node(v) from which we have already departed. So here, we can distinguish between them using the arrival time.

     • It is a forward edge (going from ancestor to descendent, u -> v), if arrival time of u will be less v

     • It is cross edge, if arrival time of u will be greater than v.

For reference:

void dfsEdges(struct graph*G, int v, int *visited, int *arrTime, int *depTime)
{
 static int time=0;


visited[v]=1;
arrTime[v]=time++;

struct node *temp = G->array[v];
while(temp!=NULL)
{
    if(visited[temp->val] != 1)
    {
        dfsEdges(G,temp->val,visited,arrTime,depTime);
    }
    else
    {
        if(depTime[temp->val] ==-1)
        printf("\n%d - %d is back edge\n",v,temp->val);
        else
        {
            if(arrTime[v]<arrTime[temp->val])
            printf("\n%d - %d is forward edge\n",v,temp->val);
            else
            printf("\n%d - %d is cross edge\n",v,temp->val);
        }

    }
    temp=temp->next;

}
depTime[v]=time++;

}