C++中的稀疏图实现和性能

Question

我目前正在研究C++中的有向图数据结构(此项目没有Boost GL).主要应用程序将识别连接的组件和接收器.预计图形是稀疏的(数字边缘的E~4V上限)并且都是均匀的权重.我试图在邻接列表,发生率列表或可能还有其他我尚未听说过的表示之间做出决定(adj.矩阵不是稀疏性的选项bc).瓶颈可能是整体空间和图形初始化的速度:图形将从潜在的巨大阵列初始化,使得阵列中的每个元素最终成为具有指向其相邻元素之一的有向边缘的顶点.要获取每个顶点的边,必须首先比较其所有相邻元素.

我的问题是:(1)表示通常更快地初始化,也快BFS遍历,(2)什么算法(比香草BFS等)是否有寻找连接组件？我知道这是O(V + E)使用BFS(这是最佳的,我认为),但我很担心中间队列的大小的图形宽度与高度呈指数增长.

没有太多的图形实现经验,所以我很感激任何建议.

Answer 1

考虑如下布局:

邻接列表可以实现为[Nx4]的数组(在这种情况下n为3,因为您说4是您的情况下的最大边数),以下列形式实现:

2  3  0  0
3  0  0  0
0  0  0  0

上面的表示假定顶点的数量按排序顺序排列,其中第一个索引到数组中(v-1).

另一方面,发生率列表要求您定义顶点列表,边缘列表和中间的连接元素(入射列表 - 图形).

正如您所说,由于您的图表非常稀疏,因此与邻接矩阵相比,两者在空间使用方面都很好.

我的建议是使用邻接列表,你可以在内存中初始化为[Nx4]连续数组(因为你说你的一个顶点最多有4个边).这种表示将更快地初始化.(此外,此表示在缓存效率方面表现更好.)

但是,如果您希望图表的大小动态且频繁地更改,则发生率列表可能会更好,因为它们通常实现为非连续空间的列表(请参阅上面的链接).在这种情况下,可能不希望取消分配和分配邻接阵列.