Edge classification in a DFS

Question

According to the book (Intro to Algorithm), in dfs, edges are classified as 4 kinds:

1. Tree Edge, if in edge (u,v), v is first discovered, then (u, v) is a tree edge.
2. Back Edge, if ......, v is discovered already and v is an ancestor, then it's a back edge.
3. Forward Edge, if ......, v is discovered already and v is a descendant of u, forward edge it is.
4. Cross Edge, all edges except for the above three.

My question is how can I identify whether v is u's ancestor or descendant when I'm trying to figure out if (u, v) is a back or forward edge?

Sacerdotal

There is a pdf that explains this also: csd.uoc.gr/~hy583/papers/ch3_4.pdf – Ashley

Answer 1

If you really need it, you can check it by maintaining so called entry and exit times for each node. During the run of the algorithm, you increment a time variable (starting from 0, of course) each time you encounter a new vertex. The times entry_t(v), exit_t(v) are initially unset for all vertices.

When you first encounter a vertex, you set entry(v):=time. When you exit a vertex by an up edge (ie. poping the vertex from the stack), you set its exit(v):=time. With that, you have

• if entry(u) is set and exit(u) is not set, then u is ancestor of the current vertex (ie. vu is a back edge)
• if entry(u)>entry(current), then u is descendant from the current vertex (current->u is a forward edge)
• otherwise, it is a cross edge

Note that these relations are made for checking during the run of the algorithm. After the algorithm has completed, a check of ancestry is basically

u is_descendant_of v = entry(u)>entry(v) and exit(u)<=exit(v)

Glarus