关于求最小生成树prim算法和cruscal算法的复杂度分析

长文预警：约1600字，总耗时（含编码，测试等）约八九个小时完成。

有人认为：“Prim算法适合稠密图，cruscal算法适合稀疏图”。我可以断言，这种说法前半句没有问题，但后半句至少在当前来看（未来计算机发展成什么样暂且不论）是非常有问题的！无论是理论分析，还是实际测试，得出的结论都能证明后半句根本没有道理。

两种算法都是贪心算法。Prim类似于dijkstra，从选定一个起始点开始，每次循环都拉一个新的点“入伙”，复杂度是min(mlogn, n^2)，（加堆优化和不加堆优化，选择复杂度小的那个即可，接近完全图的稠密图反而可能不加堆优化跑得更快）而这个log的真数也是根据不同的数据结构决定的，如果用优先队列，那么复杂度就是O(mlogm)，因为priority_queue不支持删除任意元素，当然也不支持修改任意元素，只能删除堆顶(top)的元素，所以导致大量无效元素堆积在队列中，因为我们在更新距离的时候，只能将新的距离加入队列，却无法立即删除旧的距离，最多每一条边都导致一个元素加入队列，最多m次push操作，队列中最多m个元素，所以复杂度就是O(mlogm)。而手写堆就可以删除/修改任意元素了，只要建立双向映射，找到堆中这个元素的位置即可。仍然是最多每条边更新一次答案，导致最多对堆进行m次操作（无论是加入还是修改都算作一次操作），而堆里最多n个元素，因为每个点有且仅有一个位置，不会出现优先队列当中新距离和过时的旧距离同时存在的情况。而且prim的mlogn不一定能达到上界，因为可能有很多边不会更改堆里的数据。

而cruscal算法需要对所有边排序，所以cruscal复杂度是mlogm（实际上是2mlnm，用数学归纳法和微积分算出来的，我之前发过有关这个算法的说说）。

代码及提交结果：prim优先队列cruscal仅路径压缩

通过实际运行结果，我们发现：理论复杂度低的算法并不一定实际运行速度就快。例如同时使用按秩合并和路径压缩，可以将并查集操作的单次并查集操作减到反阿克曼(n)，但它的运行速度却反而比不上只用路径压缩的log n，因为只用路径压缩就已经足够快了，也很难达到上界。再加上按秩合并反而会增加常数（并查集算法的数学证明较为复杂，略）

有人说算法和语言无关，但是算法想要在电脑上跑起来还是要借助计算机语言的。分明手写堆的理论复杂度比有点队列低，但不得不说STL就是跑得快。有了STL的加持，反而优先队列跑得比手写堆还要快。我记得在2019年我曾经用一道题试过，当时的测试结果是手写堆比优先队列快。可见时代的发展也会影响代码的运行速度。所以我也在开头说过在未来这些算法会发展成什么样我也难说。比如有可能在未来计算机运行速度的进步导致某一算法速度变快，目前它并不优秀，但在未来大放光彩也是有可能的。

根据理论分析结果，两者都是m乘log（根据换底公式，底数和真数的影响均视为常数影响），但prim算法一般达不到上界，所以我预期的是prim算法可以碾压cruscal算法，但实际运行结果却是，第一个板子题（稠密程度一般）不相上下，第二个稀疏图上prim也是仅以微弱优势取胜，和我的预期大相径庭，令我十分吃惊。我也不禁感叹，C++的sort函数就是强啊，一般来说编程语言自带的东西就是比我们手写的东西速度快的，甚至快很多。由此可见，算法的速度还是要依靠语言的。

还有就是，有些人写prim不会用堆和邻接表，只会无脑邻接矩阵，n^2暴力。如果是基于这一点，得出了”稀疏图不适合prim”这一结论，那我只能说，不会选数据结构就别赖算法，就好比某人不会开枪，然后说枪不如匕首一样可笑。那是他自己不会用，不是算法不行，好好的算法用的稀烂。

此外，此次测试结果仅作参考。图论算法的运行速度往往波动性较大，受到图的形状影响较大。尤其是最短路里面著名的SPFA算法，运气好的时候跑得巨快，运气不好就经常原地转圈，因数据更新而将已经算完的数据“返工”，非常看运气。而且就算对于同一张图，先处理哪个点，后处理哪个点，先处理哪个边，后处理哪个边也有可能导致虽然算出的结果相同，但是速度不一样。所以如果你测试的结果和我不一样，也是正常的事情。由于图的形状千奇百怪，形成的概率也各不相同，所以我们很难通过统一的数学运算算出算法运行的数学期望，也只能估算一下复杂度上界，并用实际运算结果估计数学期望了。

贴一下数学证明吧，看不懂也不重要。