# 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[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.

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 🙂

Get great deals at Amazon