# Pseudo code for constructing a spanning tree using depth-first search

empty spanning tree T
mark root as visited
push root on visit stack
while (stack not empty) {
   v = top of stack

   find unvisited neighbor w of v
   if (w exists) {
       mark w as visited
       add edge [ v, w ] to T
       push w on visit stack
       } 
    else {
       # no unvisted neighbors of top of stack
       pop top of stack
       }
    }