Post-order Graph Traversal?

Question

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

Answer 1

Post-order DFS essentially has the following design:

1. Visit the children;
2. Visit myself;

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.