2
$\begingroup$

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?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
10
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What do you mean by T U e ? $\endgroup$
    – heretoinfinity
    Apr 9, 2021 at 14:02
  • 1
    $\begingroup$ I mean T union {e} where e is the edge being considered by the algorithm at this iteration $\endgroup$
    – NaturalLogZ
    Apr 9, 2021 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.