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

Question

我想找到具有2000多个节点的图的MST。我得到的问题是我无法制作尺寸大于1500X1500的邻接矩阵（如果尺寸大于此段错误发生的原因是我们可以创建最大尺寸为10^7的数组）。这怎么能做到？

Answer 1

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

1. 你应该能够分配尺寸1500 × 1500的阵列，而不会导致段错误，只要你正确地做到这一点。如果你试图在堆栈上分配一个这样大小的数组（也就是说，作为一个局部变量），那么你可能会炸掉你的堆栈空间，这很可能是你所得到的错误。但是，如果您使用new[]或std::vector分配内存，则内存将存储在堆中，该堆旨在能够适应这样的请求。

2. 邻接矩阵只是表示图形的一种方式，而且它们被称为空间猪，如果您使用的是非常密集的图形，这只是一个真正的好主意。最常见的替代方案是邻接列表，它使用较少的存储空间，易于实现，并且支持许多相关操作比邻接矩阵更快。你可能想考虑把这个开关放在堆上而不是放在堆栈上。