How should I go about checking if my graph has at least X Minimum Spanning Trees? [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking for code must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results. See also: Stack Overflow question checklist

Closed 8 years ago.

Improve this question

I am looking for an efficient algorithm for finding if at least 'X' number of MST exist in a graph. Any pointers?

Answer 1

This doesn't flesh out a full algorithm, but the accepted answer to An algorithm to see if there are exactly two MSTs in a graph? (by @j_random_hacker) brings up a point that will probably help you a lot. Taken from his answer:

Furthermore, every MST can be produced by choosing some particular way to order every set of equal-weight edges, and then running the Kruskal algorithm.

You could probably write up an algorithm that takes advantage of this to get the number of MSTs. Well, just straight using this fact and nothing else probably doesn't get to "efficient algorithm" territory, though I imagine that any efficient algorithm is going to be taking advantage of a couple of similar facts. I'll add more results if I find any.