首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何在2000多个节点的C++中实现最小生成树?

问如何在2000多个节点的C++中实现最小生成树?
EN

Stack Overflow用户
提问于 2016-10-10 21:25:12
回答 1查看 119关注 0票数 3

我想找一个有2000多个节点的图的MST。我所遇到的问题是,我不能使邻接矩阵的大小超过1500X1500 (如果大小大于这个分段错误,因为我们可以创建一个最大10^7大小的数组)。这是怎么做到的呢?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2016-10-10 21:34:31

这里有许多问题要考虑。

  1. 您应该能够分配大小为1500×1500的数组,而不会造成分段错误,前提是要正确地进行。如果您试图在堆栈上分配一个这样大小的数组(即局部变量),那么您可能会耗尽堆栈空间,这很可能是导致所得到的错误的原因。但是,如果使用new[]或使用std::vector分配内存,则内存存储在堆中,堆设计为能够容纳这样的请求。
  2. 邻接矩阵只是表示一个图的一种方式,而且它们是空间占优势,只有当你使用非常密集的图时,它才是一个好主意。最常见的选择是邻接列表,它使用的存储空间少,易于实现,并支持比邻接矩阵更快的许多相关操作。您可能需要考虑将这些东西放到堆上,而不是堆栈上。
票数 4
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/39966977

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档