如何在 C++ 中实现超过 2000 个节点的最小生成树？
How to implement Minimum Spanning tree in C++ with more than 2000 nodes?
我想找到一个有超过 2000 个节点的图的 MST。我遇到的问题是我无法制作大小超过 1500X1500 的邻接矩阵（如果大小超过此分段错误，因为我们可以创建最大 10^7 大小的数组）。这怎么可能？
这里有很多问题需要考虑。
只要操作正确，您应该能够分配大小为 1500 × 1500 的数组而不会导致段错误。如果您尝试在堆栈上分配一个这种大小的数组（即，作为局部变量），那么您可能会耗尽堆栈 space，这很可能是导致您收到错误的原因。但是，如果您使用 new[] 或使用 std::vector 分配它，那么内存将存储在堆中，该堆旨在能够满足这样的请求。
邻接矩阵只是表示图的一种方式，它们被认为是 space 猪，只有在处理极其密集的图时才是真正的好主意.最常见的替代方案是 邻接列表 ，它使用更少的存储 space，易于实现，并且比邻接矩阵更快地支持许多相关操作。您可能需要考虑将此切换与将内容放在堆上而不是堆栈上结合起来。
我想找到一个有超过 2000 个节点的图的 MST。我遇到的问题是我无法制作大小超过 1500X1500 的邻接矩阵（如果大小超过此分段错误，因为我们可以创建最大 10^7 大小的数组）。这怎么可能？
这里有很多问题需要考虑。
只要操作正确，您应该能够分配大小为 1500 × 1500 的数组而不会导致段错误。如果您尝试在堆栈上分配一个这种大小的数组（即，作为局部变量），那么您可能会耗尽堆栈 space，这很可能是导致您收到错误的原因。但是，如果您使用
new[]或使用std::vector分配它，那么内存将存储在堆中，该堆旨在能够满足这样的请求。邻接矩阵只是表示图的一种方式，它们被认为是 space 猪，只有在处理极其密集的图时才是真正的好主意.最常见的替代方案是 邻接列表 ，它使用更少的存储 space，易于实现，并且比邻接矩阵更快地支持许多相关操作。您可能需要考虑将此切换与将内容放在堆上而不是堆栈上结合起来。