Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Edge classification in a DFS

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?

like image 533
Alcott Avatar asked Sep 09 '11 11:09

Alcott


People also ask

What are the classifications of edges in DFS of a graph?

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.

Can there be a cross edge in DFS?

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.

How many types of edges are there in depth limited search?

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.

What are the classifications of edges in a BFS graph?

Only tree edge,cross edge or back edge.


1 Answers

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)
like image 166
jpalecek Avatar answered Sep 19 '22 18:09

jpalecek