c++ - 如何在具有超过2000个节点的C++中实现最小生成树？

我想查找具有2000多个节点的图形的MST。我得到的问题是我不能使邻接矩阵的大小大于1500X1500(如果大小大于此分段错误，则因为我们可以创建最大10 ^ 7大小的数组)。怎么办呢？

最佳答案

这里有很多问题需要考虑。

只要正确执行操作，就应该能够分配大小为1500×1500的数组而不会引起段错误。如果尝试在堆栈上分配此大小的数组(即作为局部变量)，则可能会耗尽堆栈空间，这很可能是导致错误的原因。但是，如果使用new[]或std::vector对其进行分配，则内存将存储在堆中，该堆旨在容纳此类请求。

邻接矩阵只是表示图形的一种方法，众所周知它们是空间 pig ，如果您使用的是极其密集的图形，那么这确实是一个好主意。最常见的替代方案是邻接列表，该列表使用的存储空间更少，易于实现，并且比邻接矩阵更快地支持许多相关操作。您可能需要考虑将此开关与将事物放到堆而不是栈上一起使用。