8

我目前正在研究 C++ 中的有向图数据结构（此项目没有 Boost GL）。主要应用程序将识别连接的组件和接收器。这些图预计是稀疏的（E ~ 4V 上 num 边的上限）并且都是统一的权重。我正在尝试在邻接列表、关联列表或其他一些我还没有听说过的表示之间做出决定（adj. matrix 不是稀疏的选项 bc）。瓶颈可能是整体空间和图初始化的速度：图将从潜在的巨大数组初始化，这样数组中的每个元素最终都会成为一个顶点，其有向边指向其相邻元素之一。要获得每个顶点的边，必须首先比较其所有相邻元素。

我的问题是：（1）哪种表示通常初始化更快，并且 BFS 遍历也很快，（2）有哪些算法（除了普通 BFS）可以找到连接的组件？我知道使用 BFS 是 O(V+E)（我认为这是最佳的），但我担心中间队列的大小，因为图形宽度随高度呈指数增长。

对图形实现没有太多经验，因此我将不胜感激任何建议。

4

3 回答 3

5

考虑如下布局：

在此处输入图像描述

邻接列表可以实现为 [Nx4] 的数组（在这种情况下，n 为 3，而 4，因为您说 4 是您的情况下的最大边数），格式如下：

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

上面的表示假设顶点的数量是按排序顺序排列的，其中数组的第一个索引由 给出(v-1)。

另一方面，关联列表要求您定义一个顶点列表、一个边列表和它们之间的连接元素（关联列表 - 图）。

正如您所说，与邻接矩阵相比，两者在空间使用方面都很好，因为您的图非常稀疏。

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

但是，如果您希望图形的大小动态且频繁地变化，则关联列表可能会更好，因为它们通常作为非连续空间的列表实现（请参阅上面的链接）。在这种情况下，邻接数组的解除分配和分配可能是不可取的。

于 2013-03-08T01:14:43.003 回答
2

为您的目的实现图的最有效方法可能是结合每个顶点的邻接列表以及将顶点对映射到边（如果存在）的散列结构。这将需要 O(|V|+ |E|) 空间用于邻接列表， O(|E|) 用于散列结构并为您提供预期的 O(1) containsEdge(vertex v, vertex w)，insertEdge(vertex v, vertex w)并removeEdge(vertex v, vertex w)通过使用映射来获取所需的指针快速修改顶点的邻接表。

于 2013-03-08T01:35:41.733 回答
1

邻接矩阵适用于密集图，但它们被证明对于大型稀疏图是不好的选择。以下是稀疏图的简单操作的时间和空间复杂性。

稀疏图大 O 时空复杂度

考虑 100 万个节点的图的平均边数小于 4。大多数现代计算机不足以容纳邻接矩阵，因为它们的空间复杂度为 O(n*n) - 即 RAM 需要几个 TB。然而，它可以轻松安装在具有基本配置且 RAM 要求为几 MB 的廉价笔记本电脑中。

于 2018-11-20T16:44:33.483 回答