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*

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.

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 🙂

## Leave a Reply