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

Preorder and Postorder

Explore preorder and postorder traversals in the context of depth-first search for graphs. Understand how these traversals work on rooted trees and arbitrary directed graphs, how vertex states are tracked during DFS, and how edges are classified into tree, forward, back, and cross edges. This lesson helps you implement DFS with timing to analyze graph structure and vertex relationships.

We'll cover the following...

Hopefully, we’re 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 ...