According to the book (Intro to Algorithm), in dfs, edges are classified as 4 kinds:
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?
The other edges of G can be divided into three categories: Back edges point from a node to one of its ancestors in the DFS tree. Forward edges point from a node to one of its descendants. Cross edges point from a node to a previously visited node that is neither an ancestor nor a descendant.
Cross Edge: It is an edge that connects two nodes such that they do not have any ancestor and a descendant relationship between them. The edge from node 5 to 4 is a cross edge.
Output of a depth-first search Based on this spanning tree, the edges of the original graph can be divided into three classes: forward edges, which point from a node of the tree to one of its descendants, back edges, which point from a node to one of its ancestors, and cross edges, which do neither.
Only tree edge,cross edge or back edge.
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
entry(u)
is set and exit(u)
is not set, then u is ancestor of the current vertex (ie. vu is a back edge)entry(u)>entry(current)
, then u is descendant from the current vertex (current->u is a forward 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)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With