Menu
Given the directed graph below, how did we achieve the post-order traversal?
DFS
Visiting order in Pre-order traversal: 1 2 5 4 6 3
Visiting order in Post-order traversal: 4 6 5 2 1 3
817
A a postorder traversal generates nodes in the reverse of a topological sort: Algorithm: Perform a depth-first search over the entire graph, starting anew with an unvisited node if previous starting nodes did not visit every node. As each node is finished (colored black), put it on the head of an initially empty list.
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.)
Depth-First Search (DFS) Algorithms have three variants:Postorder Traversal (left-right-current) — Visit the current node after visiting all the nodes of left and right subtrees.
For Preorder, you traverse from the root to the left subtree then to the right subtree. For Post order, you traverse from the left subtree to the right subtree then to the root.
Post-order DFS essentially has the following design:
Starting at 1, the nodes are explored in the following order:
1 -> 2 -> 5 -> 4(v) ->6(v) -> 5(v) -> 2(v) -> 1(v) -> 3(v)
Here (v) implies that the node is visited now after seeing that either none of its children are left unvisited or at least they are in the pipeline for visit. This explains why the traversal is 465213.
Probably, what bothers you is how we visited the node 3 because beginning from 1 there is no path to 3. The answer to that seems that after entire connected graph has been scanned, the traversal algorithm scans if there are any unscanned nodes left. So then it ends up visiting 3 at the end.
52
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
