Does anyone knows what's the best or an acceptable algorithm to find the number of Minimum Spanning Trees in a weighted graph ? I found a paper that solves it using Kirchhoff Theorem, but I couldn't understand it.
**PS: After some tries I finally got this problem. But thanks to everyone that read it. Some hints for those who haven't solved it yet: 1 — First solve the simple version: How many spanning trees does a graph have ? 2 — Search for Kirchhoff Theorem in Wikipedia 3 — Think about what happens when we have a group of disjoint components sharing the same edge weight. **
Can you share a link to this problem?
http://www.spoj.com/problems/MSTS/