# Algorithm to get any spanning tree not necessarily a minimum spanning tree

Is there an algorithm to find a spanning tree. I know that there are $$n^{n-2}$$ of them and we have algorithms to find a minimum spanning tree.

1. But what if I just want any spanning tree? It doesn't have to be minimum.

2. For a graph with no edge weights, should I just assume that the edge weights are all 1 and then use a Kruskal's or Prim's algorithm for minimum spanning tree?

Use the BFS or the DFS algorithms. They work in $$O(n)$$ and output a spanning tree if the input is a connected graph
start with an empty set of edges T. For each edge see if $$T \,\cup \,e$$ has a cycle, if not $$T := T \,\cup \,e$$
This is $$O(m)$$ running time with the proper data structures (where m is the number of edges), which is on par with DFS and BFS theoretically. However, BFS and DFS are probably going to be faster and simpler.
• What do you mean by T U e ? Apr 9 at 14:02