是否有一种算法可以在只有k个不同边缘成本的图上找到运行时间为O（n log k）的最小生成树？

这样的算法在Skiena的算法设计书中作为练习留给读者，据推测它只是Prim算法的修改（In his wiki reference练习6-11）。任何人都可以设计此类算法是否有一种算法可以在只有k个不同边缘成本的图上找到运行时间为O（n log k）的最小生成树？

2011-02-17 ilcavero

什么是正？ n = | V | + | E |？ – 2011-02-17 22:24:00

n = | V |根据我的理解 – ilcavero 2011-02-18 03:51:56

具有简单优先级队列的Prim是O（m + n lg n），其中m是边数，n是顶点数。如果您存储具有相同优先级的条目（例如，使用链接列表），则会自动获得O（m + n lg k）。 AFAIK，这种情况下最先进的是O（m），Fredman and Willard。

2011-02-17 22:56:26

只需要清楚，我相信问题中的O（n lg k）是错误的。事实上，我在Skiena的书 – 2011-02-17 22:58:08

是的，问题应该要求O（m + n log k）。很明显，欧米茄（米）是一个下界，因为我们甚至不检查所有这些都找不到最低权重的边缘。

为了记录，约定是n表示顶点的数量，m表示边的数量。

享受我的书:-)

史蒂芬Skiena

2011-02-18 14:11:33

回答