How to find a spanning tree of a undirected graph(not necessary MST)?

Question

I know the brute force approach for solving this problem which can be given as:

1. Iterate over all edges
2. Take a set(or list)(suppose s)
3. if adding an edge to s doesn't make a cycle then add edge to s
4. End if iteration is complete over all edges.

But I want an efficient solution(time+space both) for this problem.

So, Any help will be appreciated...........

Answer 1

Assuming that the graph is connected (otherwise no spanning tree exists): Beginning from some arbitrary vertex, perform depth-first search in the graph, recording for each vertex whether it has been visited already, and outputting every edge to an unvisited vertex that you come across. These edges comprise a spanning tree since they are cycle-free and visit every vertex.

This takes O(|V|+|E|) time and O(|V|) space.