148

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

4

11 回答 11

155

这取决于问题。

邻接矩阵

  • 使用 O(n^2) 内存

  • 快速查找和检查任意两个节点之间是否存在特定边O(1)
  • 遍历所有边很慢
  • 添加/删除节点很慢；复杂的操作 O(n^2)
  • 添加新边 O(1) 很快

邻接表

  • 内存使用更多地取决于边数（更少取决于节点数），
    如果邻接矩阵稀疏，这可能会节省大量内存
  • 查找任意两个节点之间是否存在特定边
    比使用矩阵 O(k) 稍慢；其中 k 是邻居节点的数量
  • 迭代所有边的速度很快，因为您可以直接访问任何节点邻居
  • 添加/删除节点速度快；比矩阵表示更容易
  • 添加新边的速度很快 O(1)
于 2010-02-07T21:03:04.897 回答
79

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

记忆

如果内存是您最关心的问题，您可以按照这个公式来制作一个允许循环的简单图表：

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

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

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

8e > n 2 /8 当 d > 1/64

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

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

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

迭代和查找

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

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

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

于 2011-03-24T13:27:41.237 回答
34

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

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

在此处输入图像描述

于 2015-07-18T07:51:10.160 回答
21

这取决于你在寻找什么。

使用邻接矩阵，您可以快速回答有关两个顶点之间的特定边是否属于图的问题，并且您还可以快速插入和删除边。缺点是您必须使用过多的空间，尤其是对于具有许多顶点的图，这是非常低效的，尤其是在您的图稀疏的情况下。

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

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

于 2010-02-07T21:04:41.400 回答
14

假设我们有一个图，它有n个节点和m个边，

示例图
在此处输入图像描述

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

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

如果要识别所有边，则必须在矩阵上迭代，这将需要两个嵌套循环，并且需要 Θ(n 2 )。（您可以只使用矩阵的上三角部分来确定所有边，但它将再次是 Θ(n 2 )）

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

示例图的邻接表

在此处输入图像描述
您应该根据自己的需要做出选择。 由于我的声誉，我无法放置矩阵的图像，对此感到抱歉

于 2017-03-19T17:09:23.927 回答
7

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

编辑

之前关于 SO 的问题可能会有所帮助：

如何创建 ac-boost-undirected-graph-and-traverse-it-in-depth-first-search h

于 2010-02-07T23:36:57.673 回答
6

这最好用例子来回答。

以弗洛伊德-沃歇尔为例。我们必须使用邻接矩阵，否则算法会渐近地变慢。

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

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

于 2016-11-25T11:04:41.720 回答
3

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

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

对于一个完整的图，一个邻接列表（带有 64 位指针）会消耗n * (n * 64)一些内存，不包括列表开销。

对于不完整的图，邻接表会消耗0一些内存，不包括列表开销。

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

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

如果您的图表是动态更新的，您可以通过平均边数（每个节点）保持这种效率n / s。

一些带有 64 位指针和动态图的示例（动态图在更改后有效地更新问题的解决方案，而不是在每次更改后从头开始重新计算。）

对于有向图，其中n300，使用邻接表的每个节点的最佳边数是：

= 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 位指针）。

于 2012-01-23T08:59:59.887 回答
2

Depending on the Adjacency Matrix implementation the 'n' of the graph should be known earlier for an efficient implementation. If the graph is too dynamic and requires expansion of the matrix every now and then that can also be counted as a downside?

于 2014-05-08T08:36:02.707 回答
1

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

通过利用Dictionary和HashSet数据结构，可以在摊销常数时间内用EdgeExists查询表示邻接表中的图。这个想法是将顶点保存在字典中，并且对于每个顶点，我们保留一个哈希集，以引用与它有边的其他顶点。

此实现中的一个小折衷是它将具有空间复杂度 O(V + 2E) 而不是像常规邻接列表中那样的 O(V + E)，因为边在这里被表示两次（因为每个顶点都有自己的哈希集边缘）。但是诸如AddVertex、AddEdge、RemoveEdge之类的操作可以使用此实现在摊销时间 O(1) 内完成，但RemoveVertex除外，这将像在具有数组索引查找字典的邻接矩阵中一样进行 O(V) 摊销。这意味着除了实现简单之外，邻接矩阵没有任何特定优势。在这个邻接表实现中，我们可以以几乎相同的性能在稀疏图上节省空间。

详细信息请查看 Github C# 存储库中的以下实现。请注意，对于加权图，它使用嵌套字典而不是字典哈希集组合以适应权重值。类似地，对于有向图，输入和输出边有单独的哈希集。

高级算法

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

于 2017-10-13T14:59:45.307 回答
1

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

尽管运行时和空间都有一些恒定的因素开销（哈希表不如链表或数组查找快，并且需要相当多的额外空间来减少冲突）。

于 2016-11-24T18:11:04.700 回答