我正在尝试尽可能高效地实现Kruskal算法。
为了提高运行效率,使用堆或排序算法对边进行排序是否有区别?
除此之外,还有哪些技术可以使Kruskal算法更加高效?
我正在尝试尽可能高效地实现Kruskal算法。
为了提高运行效率,使用堆或排序算法对边进行排序是否有区别?
除此之外,还有哪些技术可以使Kruskal算法更加高效?
n
个顶点(即没有边)的空图G
开始,并以概率p
将每个可能的边添加到G
中,与任何其他边都无关。当组成树时,这并不完全是Kruskal算法所做的,但如果G
具有二次数量的边(以顶点数为基础),边分布不“偏向”和权重分配不“偏向”,它与之相似。