dumb_ducks's blog

Generate all spanning trees
By dumb_ducks, history, 23 months ago, In English

Hey Community, I have started to learn how to code and some algorithms. I have been stuck on finding Minimum spanning trees. I know there are Kruskals and Prims to solve this type of problem but I want to know the brute force solution to this concept. Can anyone help me by coding it in CPP, so I can understand how to generate all spanning trees.

Tags c++
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
23 months ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

Just try all combinations of selecting $$$V-1$$$ edges out of $$$E$$$ in total. Time complexity will be $$$O(V {{E}\choose{V-1}})$$$. The $$$V$$$ factor is for checking the connectivity, due to $$$V+E'=V+V-1=O(V)$$$. It might be reducible to $$$O({{E}\choose{V-1}} \log V)$$$ scale, but that would require more advanced data structures (Link-cut tree or Euler Tour Tree). I suspect that this problem would be impossible to have a solution with sub-$$$O({{E}\choose{V-1}})$$$ time complexity, as this should be a #P-complete problem (I don't have a formal proof though, anyone please provide one if you can)

→ Reply
»
23 months ago, # |
  Vote: I like it +10 Vote: I do not like it

This paper explains a way to enumerate all the spanning trees of a graph in $$$O(N + V + E)$$$ time (here $$$N$$$ is the number of spanning trees) and in $$$O(VE)$$$ space. The answer is in terms of the initial tree and the diffs between trees.

→ Reply