在 kruskal 算法中对边进行排序的最佳选择？

Question

我正在实施 Kruskal 算法，但我不确定对边进行排序的更好方法是什么。 我需要大输入（300 000+ 边）的最佳时间复杂度。 我知道它们的时间复杂度相似，但我想知道对于大输入哪个更快。

Answer 1

从使用库提供的排序函数开始。让您的解决方案发挥作用。它可能足够快。如果不是，则分析并确定是导致速度变慢的原因还是其他原因。但是请注意，除非您真的很擅长优化代码，否则您的自定义排序可能会比内置版本慢。