对于C ++中的图形问题，什么是更好的，邻接列表或邻接矩阵？

Question

对于C ++中的图形问题，什么是更好的，邻接列表或邻接矩阵？各有哪些优缺点？

Answer 1

这取决于问题。

Adjacency Matrix

• 使用OF（n ^ 2）内存
• 查找和检查是否存在特定边缘的速度很快 在任意两个节点之间O（1）
• 迭代所有边缘的速度很慢
• 添加/删除节点很慢;复杂的操作O（n ^ 2）
• 添加新边O（1）很快

Adjacency List

• 内存使用量取决于边数（不是节点数）， 如果邻接矩阵稀疏，可能会节省大量内存
• 查找任意两个节点之间是否存在特定边缘 比矩阵O（k）略慢;其中k是邻居节点的数量
• 迭代所有边缘的速度很快，因为您可以直接访问任何节点邻居
• 添加/删除节点很快;比矩阵表示更容易
• 快速添加新边O（1）

Answer 2

如果您使用哈希表而不是邻接矩阵或列表，您将获得更好或相同的大O运行时间和空间用于所有操作（检查边缘是O(1)，获得所有相邻边缘是O(degree)等） 。

对于运行时和空间都有一些常数因子开销（哈希表没有链表或数组查找那么快，并且需要相当多的额外空间来减少冲突）。

Answer 3

由于其他答案涵盖了其他方面，因此只是要讨论克服常规邻接列表表示的权衡。

通过利用Dictionary和HashSet数据结构，可以使用EdgeExists查询在分摊的常量时间中表示邻接列表中的图形。我们的想法是将顶点保留在字典中，并且对于每个顶点，我们保留一个散列集，引用其具有边缘的其他顶点。

在这个实现中的一个小的权衡是它将具有空间复杂度O（V + 2E）而不是常规邻接列表中的O（V + E），因为边缘在这里被表示两次（因为每个顶点具有其自己的哈希集合边缘）。但是AddVertex，AddEdge，RemoveEdge等操作可以使用此实现在摊销时间O（1）中完成，但RemoveVertex除外，它采用O（V）之类的邻接矩阵。这意味着除了实现简单性邻接矩阵之外没有任何特定的优势。我们可以在稀疏图上节省空间，在这个邻接列表实现中具有几乎相同的性能。

有关详细信息，请查看下面Github C＃存储库中的实现。请注意，对于加权图，它使用嵌套字典而不是字典 - 哈希集组合，以便适应权重值。类似地，对于有向图，存在用于进出边缘的单独散列集。

Advanced-Algorithms

注意：我相信使用延迟删除我们可以进一步优化RemoveVertex操作到O（1）摊销，即使我没有测试过这个想法。例如，删除时只需在字典中将顶点标记为已删除，然后在其他操作期间懒惰地清除孤立的边缘。

Answer 4

这个答案不仅适用于C ++，因为所提到的一切都是关于数据结构本身，无论语言如何。而且，我的答案是假设你知道邻接列表和矩阵的基本结构。

记忆

如果内存是您主要关注的问题，您可以按照此公式获得允许循环的简单图表：

邻接矩阵占用n2 / 8字节空间（每个条目一位）。

邻接列表占用8e空间，其中e是边数（32位计算机）。

如果我们将图的密度定义为d = e / n2（边数除以最大边数），我们可以找到“断点”，其中列表占用的内存多于矩阵：

当d> 1/64时，8e> n2 / 8

因此，使用这些数字（仍然是32位特定的），断点落在1/64处。如果密度（e / n2）大于1/64，则如果要节省内存，则最好使用矩阵。

您可以在wikipedia（关于邻接矩阵的文章）和许多其他网站上阅读此内容。

旁注：可以通过使用哈希表来提高邻接矩阵的空间效率，其中键是顶点对（仅仅是无向的）。

迭代和查找

邻接列表是仅表示现有边缘的紧凑方式。然而，这是以可能缓慢查找特定边缘为代价的。由于每个列表与顶点的程度一样长，因此检查特定边的最坏情况查找时间可以变为O（n），如果列表是无序的。然而，查找顶点的邻居变得微不足道，对于稀疏或小图，迭代邻接列表的成本可能可以忽略不计。

另一方面，邻接矩阵使用更多空间以提供恒定的查找时间。由于存在每个可能的条目，因此您可以使用索引在恒定时间内检查是否存在边。但是，邻居查找需要O（n），因为您需要检查所有可能的邻居。显而易见的空间缺点是，对于稀疏图形，添加了大量填充。有关详细信息，请参阅上面的内存讨论。

如果您仍然不确定要使用什么：大多数现实问题都会产生稀疏和/或大图，这些图更适合于邻接列表表示。它们似乎更难实现，但我向你保证它们不是，当你编写BFS或DFS并想要获取节点的所有邻居时，它们只是一行代码。但请注意，我并不是在推广邻接列表。

Answer 5

好的，我已经在图表上编译了基本操作的时间和空间复杂性。 下图应该是不言自明的。 注意当我们期望图形密集时，邻接矩阵是如何优选的，以及当我们期望图形稀疏时，邻接列表如何更可取。 我做了一些假设。问我复杂性（时间或空间）是否需要澄清。 （例如，对于稀疏图，我将En作为一个小常数，因为我假设添加一个新顶点只会添加一些边，因为我们希望图形在添加之后仍保持稀疏顶点。）

请告诉我是否有任何错误。

Answer 6

这取决于你在寻找什么。

使用邻接矩阵，您可以快速回答有关两个顶点之间的特定边是否属于图的问题，还可以快速插入和删除边。缺点是你必须使用过多的空间，特别是对于有许多顶点的图形，这是非常低效的，特别是如果你的图形很稀疏。

另一方面，对于邻接列表，更难以检查给定边是否在图中，因为您必须搜索适当的列表以找到边，但它们更节省空间。

通常，邻接列表是大多数图形应用程序的正确数据结构。

Answer 7

如果您正在查看C ++中的图形分析，可能首先要开始的是boost graph library，它实现了许多算法，包括BFS。

• Boost Graph Library Docs

编辑

关于SO的上一个问题可能会有所帮助：

how-to-create-a-c-boost-undirected-graph-and-traverse-it-in-depth-first-search

Answer 8

让我们假设我们有一个图表，其中有n个节点和m个边，

示例图

邻接矩阵：我们正在创建一个具有n个行和列的矩阵，因此在内存中它将占用与n2成比例的空间。检查名为u和v的两个节点是否在它们之间有边缘将花费Θ（1）时间。例如，检查（1,2）是代码中的边缘如下所示：

if(matrix[1][2] == 1)

如果你想识别所有边，你必须迭代矩阵，这将需要两个嵌套循环，它将采用Θ（n2）。 （您可以只使用矩阵的上三角部分来确定所有边，但它将再次为Θ（n2））

邻接列表：我们正在创建一个列表，每个节点也指向另一个列表。您的列表将包含n个元素，每个元素将指向一个列表，该列表的项目数等于此节点的邻居数（为了更好的可视化，请查看图像）。因此，它将占用内存中与n + m成比例的空间。检查（u，v）是否为边将花费O（deg（u））时间，其中deg（u）等于u的邻居数。因为最多，你必须遍历u指向的列表。识别所有边缘将采用Θ（n + m）。

示例图的邻接列表

您应该根据自己的需要做出选择。由于我的声誉，我不能把矩阵的图像，抱歉

Answer 9

最好通过示例回答这个问题。

以Floyd-Warshall为例。我们必须使用邻接矩阵，否则算法会渐近变慢。

或者如果它是30,000个顶点上的密集图形怎么办？然后一个邻接矩阵可能有意义，因为你将每对顶点存储1位，而不是每边缘16位（你的邻接列表需要的最小值）：那是107 MB，而不是1.7 GB。

但对于像DFS，BFS（以及使用它的那些，如Edmonds-Karp），优先级优先搜索（Dijkstra，Prim，A *）等算法，邻接列表与矩阵一样好。好吧，当图表密集时，矩阵可能会有一个微小的边缘，但只有一个不起眼的常数因子。 （多少钱？这是试验的问题。）

Answer 10

根据Adjacency Matrix实现，为了有效实现，应该提前知道图的'n'。如果图形过于动态并且需要时不时地扩展矩阵，这也可以算作下行？

Answer 11

添加到keyser5053的内存使用情况的答案。

对于任何有向图，邻接矩阵（每边1位）消耗n^2 * (1)位的内存。

对于complete graph，邻接列表（具有64位指针）消耗n * (n * 64)位的内存，不包括列表开销。

对于不完整的图，邻接列表使用0位的内存，不包括列表开销。

---

对于邻接列表，您可以使用以下公式来确定邻接矩阵最适合内存之前的最大边数（e）。

edges = n^2 / s确定最大边数，其中s是平台的指针大小。

如果图形是动态更新的，则可以使用n / s的平均边数（每个节点）来保持此效率。

---

一些例子（64位指针）。

对于有向图，其中n为300，使用邻接列表的每个节点的最佳边数为：

= 300 / 64
= 4

如果我们将其插入keyser5053的公式d = e / n^2（其中e是总边数），我们可以看到我们低于断点（1 / s）：

d = (4 * 300) / (300 * 300)
d < 1/64
aka 0.0133 < 0.0156

但是，指针的64位可能过度。如果你改为使用16位整数作为指针偏移，我们在断点之前最多可以容纳18个边。

= 300 / 16
= 18

d = ((18 * 300) / (300^2))
d < 1/16
aka 0.06 < 0.0625

这些示例中的每一个都忽略了邻接列表本身的开销（64*2用于向量和64位指针）。