Variations of Depth First Travesal

Question

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:

1. Push the initial node onto the stack
2. Pop the stack
3. Process the popped out node
4. Push all its adjacent nodes onto the vertex
5. Go to step 2.

Method 2. Then there is a version of depth first traversal as given in CLRS:

1. Push the node onto the stack
2. Process the pushed node
3. Push one of its adjacent node onto the stack.
4. If there is no adjacent node to the stack top node, then pop it.
5. 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:

1. The two versions yields different stack contents and processing sequence.
2. Method 1 pops out the node before pushing its neighbor. Method 2 pops out the node after all its descendants are processed.
3. 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 ?

Answer 1

Every DFS algorithm should also construct a DFS tree (or, in general, forest), which records how the search progresses. For the CLRS algorithm, the adjacent node in step 3 is made the child of the node in step 2. For the other algorithm you have to be more careful (I'll let you figure out the correct way). If the DFS tree is constructed properly, then it will satisfy the following property:

If $(x,y)$ is an edge not belonging to the tree, then either $x$ is an ancestor of $y$ or $y$ is an ancestor of $x$.

This is the property of DFS used in actual algorithms. The actual sequence in which the nodes are traversed could also be important, but this is less common.

Corneil and Krueger suggest a generic "non-deterministic" version of DFS, and give a characterization in terms of the resulting DFS traversal order. They also suggest a canonical way of forming the DFS tree given the DFS order – each node is the child of its earliest neighbor, and show that the resulting DFS tree always satisfies the crucial property stated above.

If Method 1 satisfies the criterion of Corneil and Krueger, then it is worthy of the name DFS. If you are curious, you can read the paper and check whether the criterion listed there holds for that algorithm. Even if it doesn't, you can check whether there is a simple way to construct a DFS tree (not necessarily using the construction suggested by Corneil and Krueger) that satisfies the property above – that suffices in most cases.

You can use any algorithm which satisfies your needs (in some cases, you don't care about any property, only about traversing the entire connected component). A "correct" form of DFS, together with a method of constructing the DFS tree, should satisfy the DFS tree property, and preferably also the ordering characterization of Corneil and Krueger. Which one is preferable depends on many factors – usually the one using the least resources (time and memory).