Let's say you use Kruskal's or Prim's algorithm to compute the first MST, and you want to check to see if there are other MSTs. I can do this in O(E/V) time.
The algorithm uses a priority queue (which can be constructed in O(N) ). Kruskal's and Prim's already use priority queues, but they're slower than the linear time algorithms listed below.
I know there are already algorithms that can find a single MST in linear time:
- A randomized algorithm can solve it in linear expected time. [Karger, Klein, and Tarjan, "A randomized linear-time algorithm to find minimum spanning trees", J. ACM, vol. 42, 1995, pp. 321-328.]
- It can be solved in linear worst case time if the weights are small integers. [Fredman and Willard, "Trans-dichotomous algorithms for minimum spanning trees and shortest paths", 31st IEEE Symp. Foundations of Comp. Sci., 1990, pp. 719--725.]
- Otherwise, the best solution is very close to linear but not exactly linear. The exact bound is O(m log beta(m,n)) where the beta function has a complicated definition: the smallest i such that log(log(log(...log(n)...))) is less than m/n, where the logs are nested i times. [Gabow, Galil, Spencer, and Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, vol. 6, 1986, pp. 109--122.]
I'm not sure if these algorithms use priority queues. It doesn't really matter since I could just use one of these algorithms to find the first MST in O(N) then construct a priority queue in O(N) then find all the other MSTs in O(E/V). Overall, this would take O(N).
I just came up with this algorithm for a class assignment. The algorithm my TA used to find multiple MSTs took O(N^2) or O(N^3), and so he said I should try to see if this is publishable.
Edit: I realized my algorithm only finds some of the MSTs in O(E/V). To be more specific: on all graphs, it finds some additional MSTs within time O(E/V), and I'm not sure how to find all possible MSTs.
The input to the algorithm is: 1. an MST (a list of Edge objects. Edge.weight, Edge.vertex1 and Edge.vertex2 are fields of the object). 2. A graph (a list of Edges and Verteces).
The output (for all graphs) is some (but not all) of its MSTs.
EDIT: I talked to one of the other TA's about this, and he discovered a flaw in my proof. Sorry for getting excited about this.