c++ - C++ 中的大图表示

Question

可能会有类似的问题，但我仍然有一些我无法弄清楚的部分。我正在尝试表示一个没有权重的无向图，但只有 1 表示已连接，0 表示未连接。我试图表示一个具有 80500 个节点和超过 550 万条边的图(从文件中读取)。我在想；

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

Answer 1

邻接表在空间方面更好。因为那时你只需要保存 550 万 * 2 个数字 = 11 000 000 个整数。假设您保存短整数(2 个字节)，那么您需要 22 000 000 个字节。

如果使用邻接矩阵表示，则需要保存 80500 * 80500 = 6 480 250 000 个元素。即使您将它们保存为字节，拥有 2200 万字节也比拥有超过 60 亿字节要好得多。

编辑:如果将 eges 保存为两个 4 字节整数，则有 44 000 000 个字节。如果你用 bit fiddling 非常有效地保存矩阵，那么你可以在一个字节中保存 8 个元素。但这意味着您仍然需要 810 031 250 个字节。现在差别不大，但仍然是原来的 20 倍。