CODEWITHSUNDEEP
algorithmstatic-analysis
lililqth
lililqth

Reputation: 388

What is the reverse postorder?

This is the explanation in wikipedia: Data-flow analysis

This is a typical iteration order for forward data-flow problems. In reverse-postorder iteration, a node is visited before any of its successor nodes has been visited, except when the successor is reached by a back edge. (Note that this is not the same as preorder.)

Can someone explain this in greater detail?

Upvotes: 27

Views: 21236

Answers (1)

Biboswan
Biboswan

Reputation: 1165

Reverse postordering as the name suggests produces the exact opposite of postorder traversal.

Example

enter image description here

For the above referred directed graph

postorder traversals are D B C A and D C B A

reverse postorder traversals are A C B D and A B C D

How to obtain reverse postorder traversal

One way is to run postorder traversal and push the nodes in a stack in postorder.

Then pop out the nodes to get the reverse postorder.

Application

Topological sorting using depth first search.

Upvotes: 34

Related Questions