CODEWITHSUNDEEP
treegraph-algorithmdepth-first-searchgraph-traversal
Cartoon
Cartoon

Reputation: 111

Difference between Tree Edges and Forward Edges

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.

Upvotes: 2

Views: 5187

Answers (2)

Vikas Mangal
Vikas Mangal

Reputation: 831

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++;

}

Upvotes: 4

stephan
stephan

Reputation: 527

An edge (u, v) is classified a forward edge, if discoveryTime(v) is already defined at time of v's observation and discoveryTime(u) <= discoveryTime(v). Hence the edge (u, u) is classified as forward edge, as well. The classification is based on the order DFS traversed the vertices, i.e. starting with another vertex might result in a different classification. An algorithm in pseudo code (with explanation and proof) can be found in the book Kurt Mehlhorn: Data Structures and Efficient Algorithms, Volume 2, Springer Verlag, EATCS Monographs, 1984. (out of print but made available online by the author), chapter 4, "Algorithms on Graphs", page 21, as shown below. I have included the fragment on page 25 with the edge classification (lines (8) to (10), as proposed by the author).

DFS algorithm with edge classification by [1]

Upvotes: 1

Related Questions