C++中的稀疏图实现及性能表现

Question

我目前正在使用C ++编写有向图数据结构（此项目中不使用Boost GL）。主要应用将是识别连接组件和汇点。预计图形稀疏（E〜4V上限的边数），并且所有图形的权重都将是均匀的。我正尝试在邻接表、关联表之间进行选择，或者可能是一些我还没听说过的其他表示方法（邻接矩阵由于稀疏性不是选项）。瓶颈可能将是整体空间和图形初始化速度：图形将从可能巨大的数组初始化，以使数组中的每个元素最终成为具有指向其相邻元素之一的有向边的顶点。为了获取每个顶点的边缘，必须首先比较其所有相邻元素。

我的问题是：（1）通常哪种表示法初始化速度更快，同时对BFS遍历也很快？ （2）除了普通BFS外，还有哪些算法可以用于查找连接的组件？我知道使用BFS是O（V + E）（我认为是最优的），但我担心中间队列的大小会随着高度呈指数增长而变得过大。

我没有太多与图实现方面的经验，所以我会感激任何建议。

- 42point2

---

还有普通的DFS可以用来查找组件;)但一般来说，你不能比这更快；你必须检查每条边，以决定是否需要连接某些顶点。例如，以星形、彗星（指带有路径的星形）或树为例；每条边都必须连接所有顶点。据我所知，没有比BFS/DFS更快的算法(!)，包括具有不同系数的O(|E|+|V|)算法。 - G. Bach

我猜深度优先搜索可能更好，因为中间堆栈是隐式的，而且不会像广度优先搜索中队列那样长。 - 42point2

这完全取决于图形；对于路径，队列始终只有1个元素，而堆栈将达到路径的长度。由于您的图形是稀疏的，因此您实际上可能具有与路径非常相似的子图，或者至少在BFS的每个边界上具有比最长路径更少的元素。 - G. Bach

好主意，也许值得对一些数据集进行测试。 - 42point2

Answer 1

考虑以下布局： 邻接列表可以实现为一个数组[Nx4]（在本例中n为3，4是因为你说在你的情况下4是边的最大数量），具体形式如下：

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

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

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

两者在空间使用方面都比邻接矩阵好，因为你说你的图非常稀疏。

我的建议是选择邻接表，你可以将其初始化为一个[Nx4]连续的内存数组(因为你说对于一个顶点最多有4条边)，这种表示方法比较快速。(此外，这种表示方法在缓存效率方面性能更好。)

然而，如果您预期图的大小会经常变化，则关联列表可能更好，因为它们通常被实现为非连续空间的列表(请参见上面的链接)。在这种情况下，邻接数组的释放和分配可能是不可取的。

- meyumer

---

有趣的是，我从来没有想过可以使用这种方式来表示邻接表 - 这很好，因为另一件让我担心（但没有提到）的事情就是缓存性能。结果矩阵（又称邻接表表示）仍然会非常稀疏，但绝对会比需要大量指针的链表向量表示使用更少的空间。 - 42point2

毫无疑问，这种连续的表示方式在缓存性能方面表现会更好。让我把它加到答案里。 - meyumer

Answer 2

实现图形最有效的方法可能是每个顶点使用邻接表，并且另外使用一个哈希结构将顶点对映射到边，如果存在的话。这将需要 O(|V|+ |E|) 的空间用于邻接表，O(|E|) 的空间用于哈希结构，并且通过使用映射来获取所需指针以快速修改顶点的邻接表，可以期望 O(1) 的 containsEdge(vertex v, vertex w)、insertEdge(vertex v, vertex w) 和 removeEdge(vertex v, vertex w)。请注意保留 HTML 标签。

- G. Bach

Answer 3

邻接矩阵适用于稠密图，但对于大型稀疏图来说并不是一个好选择。以下是稀疏图简单操作的时间和空间复杂度。

请参考稀疏图大O时间和空间复杂度。

考虑平均边数小于4的100万节点图。大多数现代计算机无法容纳邻接矩阵，因为它们的空间复杂度为O(n*n)，即需要几TB的RAM。而使用基本配置的廉价笔记本电脑可以轻松容纳，只需要几MB的RAM。

- Rohit Sharma