Spanning tree DFS algorithm doesn't create a tree

Question

I wrote this pseudocode to create a spanning tree from a non oriented graph (G,V), where S is a stack and v is the vertex from which we want to start the computation:

PROCEDURE SPANNING-TREE(G,v)
    S := {v}   
    while S is not empty 
        u := pop(S)
        visit u
        for each u' connected to u
            if u' is not visited
                s.push(u')
                add-edge(u,u')

For some reason this algorithm is wrong. For example let's consider this simple non oriented graph:

If we start from the first vertex, we visit it and then we push 2 and 3 into the stack and we create two edges: (1,2) and (1,3). Then we visit 3, and since it is connected to 2 which hasn't been visited yet, we also create an edge (3,2), but this creates a cycle so the computed spanning tree is not a tree. Where'e the mistake? I cannot figure another way of computing a spanning tree in O(n).

Answer 1

You can just mark a vertex as visited when you push it to the stack, not when you pop it.