Preorder and Postorder

Hopefully, you are already familiar with preorder and postorder traversals of rooted trees, both of which can be computed using depth-first search. Similar traversal orders can be defined for arbitrary directed graphs even if they are disconnected by passing around a counter, as shown below. Equivalently, we can use our generic depth-first search algorithm with the following subroutines: $Preprocess$, $PreVisit$, and $PostVisit$.

${\color{Blue} \underline{Preprocess(G):}} \\ \hspace{0.4cm} {\color{Blue} clock \rightarrow 0 }$

${\color{Red} \underline{PreVisit(v):}} \\ \hspace{0.4cm} {\color{Red} clock ← clock + 1 } \\ \hspace{0.4cm} {\color{Red} v.pre ← clock }$

${\color{Green} \underline{PostVisit(v):}} \\ \hspace{0.4cm} {\color{Green} clock ← clock + 1 } \\ \hspace{0.4cm} {\color{Green} v.post ← clock }$

$\underline{DFSAll(G):} \\ \hspace{0.4cm} {\color{Blue} clock \leftarrow 0 } \\ \hspace{0.4cm} for\space all\space vertices\space v \\ \hspace{1cm} unmark\space v \\ \hspace{0.4cm} for\space all\space vertices\space v \\ \hspace{1cm} if\space v\space is\space unmarked \\ \hspace{1.7cm} clock ← DFS(v, clock)$

$\underline{DFS(v, clock):} \\ \hspace{0.4cm} mark\space v \\ \hspace{0.4cm} {\color{Red} clock←clock+1; v.pre←clock} \\ \hspace{0.4cm} for\space each\space edge\space v\rightarrow w \\ \hspace{1cm} if\space w\space is\space unmarked \\$ ...