0
$\begingroup$

There are several graph traversal algorithms in computer science ( vis. depth first, breadth first, etc. ). Furthermore, each of these algorithms can be implemented in pre-order, in-order, and post-order.

What do those terms mean? How do I properly categorize an algorithm as pre-order, in-order, or post-order?

$\endgroup$
  • $\begingroup$ Every tree is a graph, but not every graph is a tree. Do you mean graphs in general, or just trees? $\endgroup$ – Kuba Ober Jun 20 at 15:30
1
$\begingroup$

Take a binary tree with the following structure:

Our axiomatic tree

A traversal algorithm that considers every node in a tree must consider each node in some order. It might touch the nodes in this order: 2, 1, 3. Or this order: 1, 2, 3. And so on.

We can categorize these nodes into groups for convenience. Let us say that Node 1 is the Parent Node while Node 2 and Node 3 are Children of the Parent.

When we use terms like "pre-order", "in-order", or "post-order", we are really describing the order in which our implementation of an algorithm touches the parent node.

For example, an algorithm performs a pre-order traversal of the graph above if it touches the parent node before the child nodes. ( vis 1, 2, 3 )

An algorithm performs an in-order traversal of the graph above if it touches the parent node in between the child nodes. ( vis 2, 1, 3 )

An algorithm performs a post-order traversal of the graph above if it touches the parent node after the child nodes. ( vis 2, 3, 1 )

So, when we describe an algorithm as having a particular order, we aren't necessarily describing the algorithm--but rather we are describing the implementation of the algorithm.

For example, what if we want to implement Depth-First Search (DFS) of a more complicated graph?

Here's a larger graph traversed with a pre-order implementation of DFS:

Pre-order traversal of a bigger graph

Let us say that B and G are children of F, but none of the other nodes are considered children of F.

Notice that--given that definition--every parent node is processed before it's children. There might be several nodes processed in the course of doing that, but--no matter which parent node you check, it is guaranteed to be processed before its children.

The same goes for in-order traversal ( every parent is guaranteed to be processed in between its children ):

In-order traversal of a bigger graph

And post-order traversal ( every parent is guaranteed to be processed after each of its children ):

Post-order traversal of a bigger graph

Note that all of the above are different implementations of the same algorithm, namely Depth-first Search. So, we have taken one algorithm and implemented it three different ways, each handling parents in a different order relative to their children.

In the same way, any graph traversal algorithm can be categorized as pre-order, in-order, post-order--or possibly none of the above. These terms merely describe the order in which parent nodes are processed relative to their children.

Note that the Wikipedia entry on tree traversal describes several implementations of several traversal algorithms, but is able to categorize all of these algorithms in terms of the order in which they process parents relative to their children.

$\endgroup$
  • $\begingroup$ You're describing ordered traversals of trees, but perhaps the question was more generally asked about graphs? E.g. and IIRC, directed acyclic graphs have ordered traversals, but directed cyclic graphs don't, yet at least some undirected cyclic graphs can be represented as directed acyclic graphs and thus have an ordered traversal (the conversion from directed to undirected form is trivial: forget the direction). So, once it's not about trees only, it becomes rather interesting :) $\endgroup$ – Kuba Ober Jun 20 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.