algorithm - Kruskal 算法在执行排序与使用优先级队列之间的权衡是什么？

Question

我正在学习 Kruskal 的算法，我遇到了几个不同的实现，并且想知道它们之间的权衡是什么。两种实现方式如下:

实现一- 将图中的所有边放入优先队列 PQ- 从 PQ 中移除最小边 e - 如果 e 连接了 2 个以前未连接的图组件(使用 Union Find 数据结构测试)，则将其添加到 MST- 重复直到 MST 中的边数等于图中的顶点总数 - 1

实现二- 对图中的所有边执行归并排序或快速排序- 从排序的边数组中删除最小的边然后按照上面的算法做同样的事情

所以唯一真正的区别是是使用优先级队列还是在 O(eloge) 时间内执行预先排序。

这里的权衡是什么？这两种实现对我来说似乎具有相同的运行时 - O(ElogV)。我说 logV 而不是 logE，因为连通无向图中的最大边数是 O(V^2) 和 logV^2 = 2logV，因此去除常数因子可以减少到 O(logV)。

Answer 1

两种变体具有相同的渐近复杂度。如果有很多边，使用优先级队列的实现可能会稍微好一些，因为实际上可能没有必要按权重对它们进行排序。在找到生成树之前，只需要最小的边。其余边的确切顺序无关紧要。

但是，这是否会带来节省在很大程度上取决于输入数据。例如，如果权重最高的边是最小生成树的一部分，则必须考虑所有边。实际上，我预计不会有太大差异。