用于在图中查找 MST 值的线性时间算法？
Linear time algorithm for finding value of MST in a graph?
是否有一种线性 О(n+m) 时间算法可以仅找到给定图 G(V,E) 的最小生成树的值 r？我们不想找到那个 MST，只是求它的边之和。
我已经搜索了问题的解决方案，但由于使用比较结构（UnionFind(Kruskal) 和 PQ(Prim)），Kruskal 和 Prim 的算法具有更高的复杂性。他们还找到了 MST，这是不需要的，也许有更快的方法只找到 r.
没有。没有线性解决方案。
您可以使用 disjoin-set optimizations 和 radix/counting 排序优化 Kruskal，以便复杂度为 O(E alpha(V))，其中 alpha 是一个增长非常缓慢的反阿克曼函数。对于大多数数据集，这与线性几乎没有区别。在这一点上，您可能可以通过优化代码而不是算法在 运行 时间内获得更多收益。
如果您的边是整数加权的，则 Ferdman 和 Willard 在以下出版物中提供了线性算法：
http://www.sciencedirect.com/science/article/pii/S0022000005800649
还有一个来自 Karger、Klein 和 Tarjan 的使用比较模型的随机化线性时间算法：
http://dl.acm.org/citation.cfm?doid=201019.201022
我相信在比较模型中，使用软堆的 Chazelle 算法是最快的确定性算法，但它不是线性算法（你有逆阿克曼开销）。
是否有一种线性 О(n+m) 时间算法可以仅找到给定图 G(V,E) 的最小生成树的值 r？我们不想找到那个 MST，只是求它的边之和。
我已经搜索了问题的解决方案，但由于使用比较结构（UnionFind(Kruskal) 和 PQ(Prim)），Kruskal 和 Prim 的算法具有更高的复杂性。他们还找到了 MST，这是不需要的，也许有更快的方法只找到 r.
没有。没有线性解决方案。
您可以使用 disjoin-set optimizations 和 radix/counting 排序优化 Kruskal，以便复杂度为 O(E alpha(V))，其中 alpha 是一个增长非常缓慢的反阿克曼函数。对于大多数数据集，这与线性几乎没有区别。在这一点上，您可能可以通过优化代码而不是算法在 运行 时间内获得更多收益。
如果您的边是整数加权的，则 Ferdman 和 Willard 在以下出版物中提供了线性算法： http://www.sciencedirect.com/science/article/pii/S0022000005800649
还有一个来自 Karger、Klein 和 Tarjan 的使用比较模型的随机化线性时间算法： http://dl.acm.org/citation.cfm?doid=201019.201022
我相信在比较模型中，使用软堆的 Chazelle 算法是最快的确定性算法，但它不是线性算法（你有逆阿克曼开销）。