Data Structures, Algorithms, & Applications in Java
Chapter 17, Exercise 49

We can find the depth-first spanning tree by initiating a depth-first search at vertex i. Whenever a new vertex is reached, the edge used to reach this vertex is saved in the array theTree. When the depth-first search is complete, we can verify whether or not the edges saved in theTree define a spanning tree by checking if the number of edges in theTree is n-1, where n is the number of vertices in the graph.

The code for dfSpanningTree is given below. A test program, input, and output are given in the files TestDepthFirstSpanningTree.*. 
// class data members of Graph
static Edge [] theTree;      // spanning tree edges
static int edges;            // number of edges in theTree so far

/** @return edges defining depth first spanning tree rooted
  * at vertex i in an array [0:n-2]
  * @return null iff there is no depth first spanning tree
  * @throws UndefinedMethodException if graph is directed  */
public Edge[] dfSpanningTree(int i)
{
   // make sure this is an undirected graph
   verifyUndirected("dfSpanningTree");

   int n = vertices();

   // perform a depth-first search from vertex i
   // saving edges used to reach new vertices

   // define the array reach, default initial values are 0
   reach = new int [n + 1];

   // initialize class data members
   theTree = new Edge [n - 1];      // edges in spanning tree
   edges = 0;                       // number of edges so far
   label = 1;                       // label for reached vertices

   rdfSpanningTree(i); // do the dfs

   // spanning tree found only if edges = n - 1
   if (edges == n - 1)
      return theTree;
   else
      return null;
}

/** do a depth first search from vertex v, put edges used
  * into the array theTree */
void rdfSpanningTree(int v)
{
   reach[v] = label;
   Iterator iv = iterator(v);
   while (iv.hasNext())
   {// visit an adjacent vertex of v
      int u = ((EdgeNode) iv.next()).vertex; 
      if (reach[u] == 0)  // u is an unreached vertex
      {
          // add edge (v, u) to spanning tree
          theTree[edges++] = new Edge(v, u);

          rdfSpanningTree(u);
      }  
   }
}