C++中的大图表示

Question

可能有类似的问题，但我仍有一些部分无法理解。我正在尝试用没有权重，只有1表示连接和0表示未连接的无向图来表示。我正在尝试表示一个具有80500个节点和超过550万个边的图形（从文件中读取）。我在想;

1. 如果我将我的邻接矩阵(我目前正在使用的那个)更改为邻接列表，这会有很大的影响吗？我对实现没有问题，只是问一下，是否值得把它转换为列表？
2. 由于我只存储1和0，是否有特殊的数据类型可以存储这些？ 我正在使用“in”，我认为byte数据类型会节省很多时间。
3. 除了邻接矩阵或列表之外，还有其他结构可以更好地解决这个典型问题吗？

- Ali

---

你用这个图做什么？ - Jakub Zaverka

我正在编写一个朋友推荐算法，并使用图形进行数据处理。 - Ali

Answer 1

邻接表在空间上更加优越。因为你只需要保存 5,500,000 * 2 个数字 = 11,000,000 个整数。假设你使用 short integers（2 字节），那么你需要 22,000,000 个字节。

如果你使用邻接矩阵表示它，那么你需要保存 80,500 * 80,500 = 6,480,250,000 个元素。即使你将它们保存为字节，拥有 22 百万字节也比拥有超过 60 亿字节要好得多。

编辑： 如果你将边保存为两个 4 字节的整数，那么你需要 44,000,000 个字节。 如果你使用位操作非常高效地保存矩阵，则可以在一个字节中保存 8 个元素。但这意味着你仍然需要拥有 810,031,250 个字节。现在差距不是很大了，但仍然是 20 倍以上。

- Jakub Zaverka

---

非常感谢。那么在数据类型部分，是否有比 int 更高效的东西？ - Ali

考虑以下两点：（1）可以在邻接矩阵中非常紧密地打包布尔值——需要进行一些位操作，但可以高效地使用每个位（2）对于邻接表，您将需要比16位整数更大的东西，因为“80500> 2 ^ 16”。 - user395760

每条边都由两个整数表示。因此，我们需要处理550万条边=1100万个整数。如果我们使用short int进行保存，则每个数字将占用两个字节。 1100万个数字* 2个字节= 2200万字节。你可能会感到困惑，我实际上是纠正了我之前犯的一个错误。 - Jakub Zaverka

你确实在我完成评论之前就修复了它。我后来注意到并进行了调整 :) 然而，仍然存在两个问题。 - user395760

非常感谢对这些问题的陈述。 - Ali

如果您的主要关注点是空间，那么您应该使用邻接表，但请记住，现在您可能需要花费O(n)时间来检查两个顶点是否连接。如果您可以承担使用额外内存以获得即时答案的成本，您可以为每对节点使用一个单独的位。您可能会发现这个链接有帮助：http://en.wikipedia.org/wiki/Mask_(computing)。 - Mig

Answer 2

如果你的数据不是稀疏的，那么使用邻接表可能无法节省太多空间。你可以使用带有压缩或编码行（或列，但你的图是无向图，所以压缩行更自然）的邻接矩阵来进行查找。通过压缩，你可以减少空间占用，但需要在查找时付出解压行的时间成本。

- Alex Reynolds