求图中MST值的线性时间算法？
是否有线性 О（n m） 时间算法来仅查找给定图形 G（V，E） 的最小生成树的值 r？我们不想找到那个MST，只是它的边缘之和。
我已经搜索了问题的解决方案，但Kruskal和Prim的算法具有更高的复杂性，因为它们使用了比较结构（UnionFind（Kruskar）和PQ（Prim））。此外，他们还找到了MST，这是不需要的，也许有更快的方法只找到r。
共有2个答案
不。没有线性解决方案。
您可以使用分离集优化和基数/计数排序来优化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的使用软堆的算法是最快的确定性算法，但它不是线性的(你有一个逆Akermann开销)。
-
本文向大家介绍C++线性时间的排序算法分析，包括了C++线性时间的排序算法分析的使用技巧和注意事项，需要的朋友参考一下 前面的文章已经介绍了几种排序算法，如插入排序（直接插入排序，折半插入排序，希尔排序）、交换排序（冒泡排序，快速排序）、选择排序（简单选择排序，堆排序）、2-路归并排序（可以参考前一篇文章：各种内部排序算法的实现）等，这些排序算法都有一个共同的特点，就是基于比较。 本文将介绍三种非
-
问题内容： 通常，一些答案提到给定的解决方案是 线性的 ，或者另一个是 二次的 。 如何发挥作用/识别什么？ 有人能为像我这样仍然不认识的人解释这种最简单的方法吗？ 问题答案： 当所需时间随所涉及元素的数量线性增加时，该方法是线性的。例如，用于打印数组元素的for循环大致是线性的： 因为如果我们打印range（100）而不是range（10），则运行它所需的时间要长10倍。您会经常看到写为O（N）
-
Mst是一款Python2.7编写的小漏洞利用平台，可运行在windows | Backtrack | maxosx 等系统，专注于web漏洞的测试和各种利用插件的编写。 不懂怎么介绍，来看下截图吧~ 在windows上运行: Backtrack:(需要注意=>执行请输入命令python2.7 mst.py 你懂的) MacosX:
-
问题是我需要一个简化版本的算法，可以计算一个二值图像中几个白色轮廓的质心。例如，如果只有一个白色轮廓，则使用公式计算轮廓中心的坐标Xc和Yc： 其中M是强度m_i的和，m_i是像素强度值，x_i和y_i是像素在图像上的位置，n是像素总数。 有没有人可以建议一些类似的方法来处理几个轮廓，或者如何在计算其中一个轮廓时忽略其他的轮廓，使用相同的公式？
-
脚本： 一群汽车从北向南（viceversa）沿着一条双车道道路行驶。过了一会儿，他们到达了一座桥。这座桥是单向的，通行能力有限。一辆汽车花100毫秒通过这座桥。不允许发生交通碰撞。 假设我需要计算，对于所有的车， 从车辆请求进入桥梁到开始穿越之间的时间。 例如：如果一辆向北行驶的汽车到达桥上，发现桥上有汽车向南行驶，它必须等待。它需要等多久？当然，如果只有一辆车（桥是空的），汽车的等待时间=0。
-
给我一个图中名为“a”的顶点，对于v中的每一个v，我需要找到从a到v的路径的权重，它在时间O(v+E)中权重最低。我不得不只使用BFS或DFS（尽管这很可能是BFS的问题）。 我想过要制作一个新的图，其中边为0的顶点是统一的，然后在它上面运行BFS，但是这会破坏图的方向（如果图是无向的或者权重是{2,1}，对于边为2，我会创建一个新的顶点）。 如果有任何帮助，我将不胜感激。 谢谢