Is there an algorithm to find a minimum spanning tree that runs in time O(n log k) on a graph that has only k different edges costs?

Such algorithm was left as an exercise to the reader in Skiena's algorithm design book, su开发者_高级运维pposedly it is just a modification of Prim's algorithm (In his wiki reference exercise 6-11). Can anyone design such algorithm?

Yes, the problem should ask for O(m + n log k). Clearly Omega(m) is a lower-bound, since we cannot even find the lowest-weight edge without checking all of them.

For the record, the convention is that n denotes the number of vertices and m the number of edges.

Enjoy my book :-)

Steven Skiena

Prim with a simple priority queue is O(m+n lg n), where m is the number of edges and n the number of vertices. If you bucket entries with the same priority (e.g., use linked lists) you automatically get O(m+n lg k).

AFAIK, the state of the art for this case is O(m), Fredman and Willard.