While learning depth first traversal, I realise there are two approaches that are followed.
Method 1. The first one is as given in the Forouzan's book is as follows:
- Push the initial node onto the stack
- Pop the stack
- Process the popped out node
- Push all its adjacent nodes onto the vertex
- Go to step 2.
Method 2. Then there is a version of depth first traversal as given in CLRS:
- Push the node onto the stack
- Process the pushed node
- Push one of its adjacent node onto the stack.
- If there is no adjacent node to the stack top node, then pop it.
- Go to step 2.
CLRS does not explain it in terms of push and pop operation on stack. However I made this push pop version equivalent to CLRS Depth First traversal explanation. This approach is also explained in this video.
I observe the following points:
- The two versions yields different stack contents and processing sequence.
- Method 1 pops out the node before pushing its neighbor. Method 2 pops out the node after all its descendants are processed.
- Method 1 pushes all adjacent nodes and processes the stack top node while method 2 pushed one adjacent node, processes it, pushes its adjacent node. This results in different processing sequence, as can be seen below:
So which one is correct/preferable ?