Types of edges involved in DFS and relation between them

Describe types of edges involved in DFS of a tree and directed & undirected graph and establish relation between them.


Prerequisite: Arrival and Departure Time of Vertices in DFS
 


 
Depth-First search in a tree

For a tree, Depth-First search is simple preorder or postorder traversal and it contains only Tree Edges. If x is a descendant of y, then the relation between the arrival and departure time for tree edges of DFS is

arrival[y] < arrival[x] < departure[x] < departure[y]
 

Depth-First search in an undirected graph

With the graph version of DFS, only some edges will be traversed and these edges will form a tree, called the depth-first-search tree of graph starting at the given root, and the edges in this tree are called Tree Edges. There is one other type of edge called Back edge which point from a node to one of its ancestors in the DFS tree.

For an edge u -> v in an undirected graph, the relation between the arrival and departure time for tree edges and back edges is as illustrated from below diagram -

Tree edge
arrival[v] > arrival[u]
departure[u] > departure[v]

For example, edge 0 -> 1 forms a tree-edge as 0 < 1 and 11 > 10

Back edge
arrival[v] > arrival[u]
departure[u] > departure[v]

For example, edge 0 -> 2 forms a back-edge as 0 < 3 and 11 > 8
Similarly, 3 -> 5 forms a back-edge as 2 < 5 and 9 > 6

  undirected-graph-arrival-departure-time

The code for finding arrival and departure time in an undirected graph can be seen here.
 

Depth-First search in a directed graph

There are two other categories of edges of graph that can be found while doing DFS in a directed graph -

Forward edges that points from a node to one of its descendants.
Cross edges that points from a node to a previously visited node that is neither an ancestor nor a descendant.
  
Types of edges involved in DFS and relation between them

For an edge u -> v in an directed graph, an edge is a tree edge if parent[v] = u. For the other types of edges, we can use their arrival and departure times to tell whether v is an ancestor, descendant, or distant cousin of u. Below are the relation between the arrival and departure time for different types of edges involved in a DFS of directed graph -

Tree edge
arrival[v] > arrival[u]
departure[u] > departure[v]

Back edge
arrival[u] > arrival[v]
departure[u] < departure[v]

Forward edge
arrival[v] > arrival[u]
departure[u] > departure[v]

Cross edge
arrival[u] > arrival[v]
departure[u] > departure[v]

For tree edge, back edge and forward edges, the relation between the arrival times and departure times of the endpoints is immediate from the tree structure. For any cross edge, u is neither an ancestor nor descendant of v. So we can say that u and v's intervals do not overlap. i.e. for an edge u -> v,

arrival[v] < departure[v] < arrival[u] < departure[u]

Please note we cannnot have an edge from v -> u. If any such edge was there, it would have formed the Tree Edge.
 

References:
http://www.cs.yale.edu/homes/aspnes/pinewiki/DepthFirstSearch.html

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂