c++ - 如何存储这种图形？

Question

假设我们有一个双向边图，没有权重。我怎样才能存储它，这样我就不会浪费大量内存，让它变得更快并且可以快速访问每个顶点的邻居？我的意思是，直到现在这样的事情:{(1,2)(1,5)(1,3)(2,4)(2,3)} 我一直在使用数组: array[1][2]=1 表示 1 和 2 之间存在联系。这有两个问题:

• a) 由于图是双向的，(1,2) 意味着 (2,1) 也存在。如果我想稍后轻松访问 2 的邻居，我必须在每次迭代中进行两项更改:array[1][2]=1、array[2][1]=1

• b) 当我知道某个顶点(比如 5)只剩下一个邻居时，我必须搜索整个 array[5][x] 检查每一个可能的 x

• c) 对于一百万个顶点的图，这个怪物变得太大而无法在任何比赛中使用

你能帮我解决我的问题吗？

Answer 1

看起来你想要一张集合的 map 。

std::map< int, std::set< int > >

因此，对于一个整数，您可以将其所有邻居的集合存储在集合中。您将需要函数来操作此集合。

如果节点数是可数的，即它们的范围从 0 到 N 并包括所有这些数字，那么您可以使用 std::vector< std::set<int> >这样做会更有效率。您也可以使用 std::vector< std::bitset<N> >或 std::vector< boost::dynamic_bitset > >例如，如果您有 20,000 个节点，因此可以负担得起 20,000 个 2500 字节的位集(加上一些开销)，每个 = 50MB 内存(大约)。

与您现有的模型相比，这是一个稍微紧凑的模型，但不是很多。如果你有一百万个顶点，那么它大约有 125GB，所以显然你不能使用这个模型，但应该使用这个集合。此外，迭代一个顶点以查看它的邻居是什么是一个比位集快得多的集合操作。

除非有许多完全没有邻居的顶点并且它们是按顺序编号的，否则 map 相对于 vector 没有优势。

不确定您称之为“吨”的内存有多少。我刚刚列出的模型使用常量内存，而集合映射使用的内存与您拥有的邻里关系的数量成正比，但当它变满时，它的紧凑性远不如位集 vector ，因此会消耗更多。