Preorder and Postorder

This counts the order in which a node is first visited, and is finished being visited. We essentially define a global counter before calling dfs() and for each node, we determine the pre and post orders using the following algorithm.

procedure explore(G,v)
Input: A graph G = (V,E) and a start vertex v in V
Output: visited(u) is set to true for all u reachable from v
visited(v) = true
pre(v) = clock
clock++
for each edge (v,u) in E:
	if not visited(u):
		explore(G,u)
post(v)=clock
clock++

There is the concept of preorder, postorder, and inorder Binary Tree Traversal since a tree is just a specialized graph. I use this in Leetcode - Construct Binary Tree from Preorder and Inorder Traversal.

We represent the pre and post order numbers for a vertex as such: [pre, post]. Using these sets, their intervals need to satisfy one of the following properties which determines that type of edge lies between two vertices:

1. Tree edge: $(u,v)$ is a tree edge if it is in the Depth First Search forest and $I_v\subset I_u$
2. Forward edge: $(u,v)$ is a forward edge if it is not in the DFS forest and $I_v\subset I_u$
3. Back edge: $(u,v)$ is a back edge if $I_u\subset I_v$ where this cannot be in the DFS forest
4. Cross edges: $(u,v)$ is disjoint if $I_u$ and $I_v$ are disjoint.