在 C + + 中，用邻接列表还是邻接矩阵来解决图问题，哪个更好？

对于 C + + 中的图形问题，邻接列表和邻接矩阵哪个更好？ 每种方法的优点和缺点是什么？

179936 次浏览
小开

那要看是什么问题了。

邻接矩阵

  • 使用 O (n ^ 2)存储器
  • 它是快速查找和检查是否存在一个特定的边缘
    在任意两个节点 O (1)之间
  • 在所有边上迭代是很慢的
  • 添加/删除节点的速度很慢; 这是一个复杂的操作 O (n ^ 2)
  • 增加一个新的边 O (1)是很快的

邻舍名单

  • 内存使用更多地取决于边的数量(而较少取决于节点的数量) ,
    如果邻接矩阵很稀疏的话可以节省很多内存
  • 查找任意两个节点之间是否存在特定的边
    略慢于矩阵 O (k) ，其中 k 是邻接节点的个数
  • 遍历所有边很快，因为可以直接访问任何节点邻居
  • 添加/删除节点非常快; 比矩阵表示更容易
  • 快速添加一个新的边 O (1)
小开

这取决于你要找什么。

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

另一方面，使用 < em > 毗邻名单 很难检查给定的边是否在图中，因为您必须通过搜索适当的列表才能找到边，但是它们更加节省空间。

一般来说，邻接列表是大多数图形应用程序的正确数据结构。

小开

如果您正在查看 C + + 中的图形分析，那么可能首先要从 升级图形库升级图形库开始，它实现了包括 BFS 在内的许多算法。

剪辑

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

如何创建一个-c-Boost-无向图并遍历它-深度优先搜索

小开

这个答案不仅适用于 C + + ，因为上面提到的所有内容都是关于数据结构本身的，与语言无关。我的答案是假设你们知道邻接列表和矩阵的基本结构。

记忆

如果内存是你主要关心的问题，那么你可以遵循这个公式得到一个允许循环的简单图形:

邻接矩阵占据 n2/8字节空间(每个条目一位)。

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

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

8e > n2/8 < strong > d > 1/64

因此，有了这些数字(仍然是32位特定的) ，断点就会到达 1/64。 如果密度(e/n2)大于1/64，那么如果希望节省内存，则使用 矩阵更可取。

你可以在 维基百科(关于邻接矩阵的文章)和许多其他网站上读到这一点。

边注 : 可以通过使用哈希表来提高邻接矩阵的空间效率，哈希表中的键是一对对顶点(只是无向的)。

迭代和查找

邻接列表是一种仅表示现有边的简洁方法。然而，这样做的代价是可能会减慢特定边缘的查找速度。由于每个列表只要一个顶点的度，如果列表是无序的，那么检查特定边的最坏情况查找时间可能变成 O (n)。 然而，查找顶点的邻居变得很简单，对于一个稀疏或小的图，遍历邻接列表的代价可能是可以忽略不计的。

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

如果你仍然不确定使用什么 : 大多数现实世界的问题产生稀疏和/或大图，这更适合于邻接列表表示。它们可能看起来很难实现，但是我向您保证它们不是，当您编写 BFS 或 DFS 并希望获取一个节点的所有邻居时，它们只需要一行代码。但是，请注意，我并不是在一般情况下推广邻接列表。

小开

添加到 keyser5053关于内存使用的答案。

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

对于 完全图完全图，邻接列表(带有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位指针)。

小开

根据不同的邻接矩阵实现，应该更早地知道图表的 n’，以便更有效地实现。如果图表太动态，需要不时地扩展矩阵，那也可以算作是一个缺点？

小开

好了，我已经汇编了图表上基本运算的时间和空间复杂度。
下面的图片应该是不言而喻的。
注意当我们期望图是密集的时候邻接矩阵是多么的可取，当我们期望图是稀疏的时候邻接列表是多么的可取。
我做了一些假设。问我复杂性(时间或空间)是否需要澄清。(例如，对于一个稀疏图形，我把 En 当作一个小常数，因为我假设添加一个新的顶点只会添加几条边，因为我们期望图形在添加了那个顶点之后仍然保持稀疏。)

如果有什么错误请告诉我。

enter image description here

小开

如果你使用哈希表来代替邻接矩阵或列表，你会得到更好的结果，或者所有操作的大 O 运行时和空间都是相同的(检查一个边是 O(1)，得到所有相邻的边是 O(degree)，等等)。

不过，对于运行时和空间而言，都存在一些常数开销(哈希表不像链表或数组查找那样快，并且需要相当大的额外空间来减少冲突)。

小开

最好用例子来回答这个问题。

想想 Floyd-Warshall，我们必须使用一个邻接矩阵，否则算法会渐近地变慢。

或者，如果它是一个有30,000个顶点的密度图呢？然后一个邻接矩阵可能是有意义的，因为你将存储每对顶点1比特，而不是每边16比特(最低需要一个邻接列表) : 这是107 MB，而不是1.7 GB。

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

小开

假设我们有一个图，它有 N个节点和 我个边,

示例图
enter image description here

邻接矩阵 我们正在创建一个矩阵，它有 N数量的行和列，因此在内存中它将占用与 n2成比例的空间。检查两个名为 你和 翻译的节点之间是否有边缘需要 Θ (1)时间。例如，检查(1,2)是否是一条边，如下代码所示:

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

如果你想识别所有的边，你必须遍历矩阵，这需要两个嵌套循环，它取 Θ (n2)。(你可以使用矩阵的上三角形部分来确定所有的边，但是它仍然是 Θ (n2))

相邻名单: 我们正在创建一个列表，每个节点也指向另一个列表。您的列表将包含 N元素，并且每个元素将指向一个列表，该列表的项数等于该节点的邻居数(查看图像以获得更好的可视化效果)。所以它占用的内存空间与 N + m成正比。检查(u，v)是否是一条边将需要 O (deg (u))时间，其中 deg (u)等于 u 的邻居数。因为最多只能迭代 u 指向的列表。识别所有的边将需要 Θ (n + m)。

示例图的邻接表

enter image description here
你应该根据自己的需要做出选择。 因为我的名声，我不能把矩阵的形象，对不起

小开

我只是想谈谈克服常规邻接列表表示法的权衡，因为其他答案已经涵盖了这些方面。

利用 字典和 HashSet数据结构，可以在固定时间内用 边缘存在查询表示邻接表中的图。我们的想法是在字典中保存顶点，对于每个顶点，我们保存一个引用其边的其他顶点的哈希集。

这个实现的一个小的折衷是，它将具有空间复杂度 O (V + 2E) ，而不是常规邻接列表中的 O (V + E) ，因为边在这里表示两次(因为每个顶点都有自己的散列边集)。但是像 AddVertex，AddEdge，RemoveEdge这样的操作可以通过这个实现在分摊时间 O (1)中完成，除了 移除顶点，它将像数组索引查找字典一样在邻接矩阵中分摊 O (V)。这意味着除了实现的简单性，邻接矩阵没有任何特定的优势。我们可以节省空间的稀疏图与几乎相同的性能在这个邻接列表实现。

有关详细信息，请参阅下面 Github C # 存储库中的实现。注意，对于加权图，它使用嵌套字典代替字典-哈希集合组合，以适应加权值。类似地，对于有向图，有单独的散列集用于输入和输出边。

高级算法

注意: 我相信使用延迟删除我们可以进一步优化 移除顶点操作到 O (1)摊销，即使我还没有测试这个想法。例如，删除时只需在 dictionary 中将顶点标记为已删除，然后在其他操作期间延迟地清除孤立边。


提交答案