Search⌘ K
AI Features
Home
Courses
Mastering Algorithms for Problem Solving in Python

Preorder and Postorder

Explore preorder and postorder traversal techniques using depth-first search on graphs. Understand the timing and classification of vertices and edges during DFS, including concepts like active intervals and ancestor-descendant relationships. This lesson helps you implement DFS with traversal orders and analyze graph structures effectively.

We'll cover the following...

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: PreprocessPreprocess, PreVisitPreVisit, and PostVisitPostVisit.

Algorithm

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

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

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

DFSAll(G):‾clock←0for all vertices vunmark vfor all vertices vif v is unmarkedclock←DFS(v,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)

DFS(v,clock):‾mark vclock←clock+1;v.pre←clockfor each edge v→wif w is unmarkedw.parent←vclock←DFS(w,clock)clock←clock+1;v.post←clockreturn clock \underline{DFS(v, ...