Graph Has Two / Three Different Minimal Spanning Trees?

Question Detail: 

I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal spanning trees. The naive solution that I've though about is running Kruskal's algorithm once and finding the total weight of the minimal spanning tree. Later , removing an edge from the graph and running Kruskal's algorithm again and checking if the weight of the new tree is the weight of the original minimal spanning tree , and so for each edge in the graph. The runtime is O(|V||E|log|V|) which is not good at all, and I think there's a better way to do it.

Any suggestion would be helpful, thanks in advance

Asked By : itamar

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12048

Answered By : Luke Mathieson

Kapoor & Ramesh (proper SIAM J. Comput. version, free(?) personal website version) give an algorithm for enumerating all minimum spanning trees in both weighted and unweighted graphs.

My understanding of the basic idea is that you start with one MST, then swap edges that lie along cycles in the graph (so as long as the weights are okay, you're replacing one edge with another that you know will reconnect the tree).

For the weighted case they give a running time to list all minimum spanning trees of $O(N\cdot|V|)$ where $N$ is the number of such spanning trees. It enumerates them in order of increasing weight, and my current (cursory) understanding suggests that it's perfectly feasible to terminate the algorithm after it has generated a given number of trees (as it just starts with the MST and produces them sequentially).