时间戳

首页 > 解决方案 > 简单无向图的表示

c++ - 简单无向图的表示

问题描述

我需要你的专业知识：

我即将在 C++ 中实现一个图形类并考虑正确的表示。这些图简单且无向。顶点的数量现在最多可达 1000 个，但将来可能会更高。边数高达 200k 甚至更高。每个顶点都有一个颜色（int）和一个id（int）。边传输的信息不比连接到顶点的信息多。

我存储图表，只需要访问 x 和 y 是否连接 - 这是我经常需要的。初始化后，我永远不会删除或添加新的顶点或边（N = 顶点数，M = 从一开始就给出的边数）！

我已经可以使用的一种表示形式：

一个邻接列表展开成一个长长的列表。除了这个表示之外，还有一个数组，其中包含每个顶点的起始索引。存储 O(2M) 并检查 x 和 y 之间的边缘是否平均为 O(n/m)

我想到的一个表示：

这个想法是，而不是将邻接列表展开到一个数组中，而是使用邻接矩阵来完成。那么存储 O(N^2)？是的，但我想在一个字节之外的一位中存储一个边。（实际上是对称的 2 位）示例：假设 N=8，然后创建一个长度为 8（64 位）的向量<uint8_t>。在 0 上初始化每个条目。如果顶点 3 和顶点 5 之间有一条边，则将 pow(2,5) 添加到属于顶点 3 的向量的条目并对称。因此，当 3 和 5 之间有一条边时，在顶点 5 的位置处的顶点 3 的条目中有一个 1。将我的图插入这个数据结构后，我认为应该能够在恒定时间内访问邻域二元运算：3 和 5 是否相连？是，如果 v[3] ^ pow(2,5) == 0。当顶点数多于 8 时，

您如何看待第二种解决方案 - 它是否可能已经知道并正在使用？考虑 O(1) 的访问我错了吗？没有真正的性能改进是否需要付出很多努力？

将两种表示加载到一个大列表中的原因是由于有人告诉我缓存改进。

我很高兴收到关于这个想法的一些反馈。我可能会走得很远 - 在这种情况下请善待：D

标签： c++data-structuresgraphdiscrete-mathematics

解决方案

具有 200,000 条边的 1000x1000 矩阵将非常稀疏。由于图是无向的，矩阵中的边将被写入两次：

VerticeA -> VerticeB   and   VerticeB -> VerticeA

您最终将填满矩阵的 40%，其余的将是空的。

边缘

The best approach I can think of here is to use a 2D vector of booleans:

std::vector<std::vector<bool>> matrix(1000, std::vector<bool>(1000, false));

The lookup will take O(1) time and std::vector<bool> saves space by using a single bit for each boolean value. You will end up using 1Mbit or ~128kB (125 kB) of memory.

The storage is not necessarily an array of bool values, but the library implementation may optimize storage so that each value is stored in a single bit.

This will allow you to check for an edge like this:

if( matrix[3][5] )
{
    // vertice 3 and 5 are connected
}
else
{
    // vertice 3 and 5 are not connected
}

Vertices

If the id values of the vertices form a continuous range of ints (e.g. 0,1,2,3,...,999) then you could store the color information in a std::vector<int> which has O(1) access time:

std::vector<int> colors(1000);

This would use up memory equal to:

1000 * sizeof(int) = 4000 B ~ 4 kB (3.9 kB)

On the other hand, if the id values don't form a continuous range of ints it might be a better idea to use a std::unordered_map<int, int> which will on average give you O(1) lookup time.

std::unordered_map<int, int> map;

So e.g. to store and look up the color of vertice 4:

map[4] = 5;            // assign color 5 to vertice 4
std::cout << map[4];   // prints 5

The amount of memory used by std::unordered_map<int, int> will be:

1000 * 2 * sizeof(int) = 8000 B ~ 8 kB (7.81 kB)

All together, for edges:

Type Memory Access time
std::vector<std::vector<bool>> 125 kB O(1)

and for vertices:

Type Memory Access time
std::vector<int> 3.9 kB O(1)
std::unordered_map<int, int> 7.8 kB O(1) on avg.

推荐阅读