Variations of Depth First Travesal
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).