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[u] < arrival[v]`

`departure[u] > departure[v]`

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

**Back edge:**

`arrival[u] > arrival[v]`

`departure[u] < departure[v]`

*For example, edge 2 -> 0 forms a back-edge as 3 > 0 and 8 < 11*

*Similarly, 5 -> 3 forms a back-edge as 5 > 2 and 6 < 9*

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[u] < arrival[v]`

`departure[u] > departure[v]`

**Back edge:**

`arrival[u] > arrival[v]`

`departure[u] < departure[v]`

**Forward edge:**

`arrival[u] < arrival[v]`

`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 cannot 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

Back Edge definition changes in the article. Please correct it

Thanks Abhishek. We have corrected it.

why u not mentioned the code of this algorithm???

Hitesh, this post doesn’t meant to have any code. But the concepts covered in this post will be used in subsequent problems.