C++中的大图表示

Question

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

1. 如果我将邻接矩阵(我正在使用的那个)更改为邻接列表,是否会产生巨大的影响.我对实现没有任何问题,只是问它是否值得将它转换为列表？
2. 因为我只存储1和0是一个特殊的数据类型没有存储这个.我正在使用,我猜一个字节数据类型将节省大量时间.
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 字节。如果您通过位调整非常有效地保存矩阵，那么您可以在一个字节中保存 8 个元素。但这意味着您仍然需要 810 031 250 字节。现在差别不大，但仍然是20倍多。