Preorder and Postorder

Hopefully, you are already familiar with the 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)$

$$\begin{gathered} \underset{‾}{DFS(v,clock):} \\ markv \\ clock\leftarrow clock+1;v\mathrm{.}pre\leftarrow clock \\ foreachedgev\to w \\ ifwisunmarked \\ w\mathrm{.}parent\leftarrow v \\ clock\leftarrow DFS(w,clock) \\ clock\leftarrow clock+1;v\mathrm{.}post\leftarrow clo \end{gathered}$$ ...