# 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?

## 3 Answers

Use the BFS or the DFS algorithms. They work in $$O(n)$$ and output a spanning tree if the input is a connected graph

Just do a graph traversal algorithm, like DFS or BFS.

While I agree with the other answers as the "best" way to find a spanning tree, your intuition to just assume all edge weights are 1 and then use an algorithm for MST is also good. Prim's and Kruskal's algorithms are both quite fast. In particular, if you avoid sorting the edges by weight (which you know you don't have to do because you set all the weights to 1, Kruskal's algorithm just becomes:

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, 2021 at 14:02
• I mean T union {e} where e is the edge being considered by the algorithm at this iteration Apr 9, 2021 at 18:05