algorithm - 在空间图上执行 Kruskal 算法的最佳数据结构？

Question

如果对空间没有限制，考虑到图是稀疏的，那么选择执行 kruskals 算法的最佳数据结构是什么。

我正在考虑使用单链表实现

Answer 1

是的。:-) 不幸的是，对于这个学生来说，这个问题的提出很糟糕，因为它没有提供与手头问题相关的其他操作的详细信息。如果图已经存在，那么一堆排序将是合适的；然而，图的构造是问题的一部分，因此基于权重以线性顺序存储边更佳。这使得 Kruskal 的算法更快。

Answer 2

这听起来像是滑铁卢大学 ECE 250 的学生。不幸的是，项目截止日期已经结束。