我目前正在处理图形实现的性能问题。
使用的技术
它是用 C++ 编程的。目前，图是通过 BGL 实现的。
关于图表
托管图是动态且无向的。它有两种结构：很多完全子图和很少的单边。唯一需要的信息是顶点的直接邻域。
问题陈述
一开始，完整的子图很小（大约 10 个顶点）和众多（大约 13k）。BGL 的邻接表实现是完美的。但是现在，它被要求管理几个 5000 个顶点的子图。这意味着 5000x5000 边缘。现在时间和空间上的表现都很差。
被拒绝的解决方案
我的第一个想法是使用 BGL 提供的邻接矩阵实现。但它不允许动态图。为了解决这个限制，有两种解决方案：为动态图提供邻接矩阵的新实现或在静态图中使用可用顶点池。经过反思，我认为这不是一个好主意：空间复杂度仍然是VxV/2。
最终解决方案和问题
所以，这是我的最终解决方案：不要使用 BGL，实现顶点袋来表示完整的子图（不需要边）并直接连接几个单边的顶点。通过这样做，最大子图的空间复杂度下降到它的顶点数，大约为 5000。
- 你认为最后一个解决方案是好的吗？
- 如果没有，我可以使用哪种实现？为什么？
更新 1
有关该图的更多信息：该图具有约 100k 个顶点，约 3 个顶点的约 13k 个完整子图，以及约 100 个大小范围 [10-5000] 的完整子图。每个边缘都有捆绑的属性。
更新 2
感谢Salim Jouilli ，我最近了解到节点包是超图的一种坦率方法，其中超边包含在节点的子集中。
更新 3
我已经完成了解决方案的实施。我有效地提高了内存消耗和运行时间：从 6GB 到 24MB，从 50 分钟到 2 分钟 30 分钟。