Post-order Graph Traversal? [closed]

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

Ruffianism

I'm voting to close this question as off-topic because it is not a programming question. It appears to be a question about algorithm theory. – Ecclesiastes

I'm voting to close this question as off-topic because it is not about programming. – Eutherian

How is an algorithm not programming? We'll not be able to discuss design patterns next. This close is wrong in my opinion. Vote to open. – Langobard

@Liam, this may explain why there are so many buggy applications around: some programmers nowadays seem to consider algorithms as someone else's problem ;-) – Ernst

it is too broad as well as no mcve, multiple off-topics – Eutherian

@JarrodRoberson I think there' s exactly one correct answer so it's not too broad. MCVE is n/a to this question. Usually we require MCVEs for solving bugs in code. – Isidraisidro

Is this a homework assignment? – Anthropoid

Are you sure about answer correctness for post-order?! – Ay

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.

Gipps