algorithm - Graph 数据结构的最坏情况内存

Question

我可以在许多书中看到，图形的最坏情况内存要求是 O(V)。但是，如果我没记错的话，图通常表示为邻接矩阵，而不是通过创建节点（如链表/树）。因此，对于包含 5 个顶点的图，我需要 5x5 矩阵，即 O(V^2)。他们为什么说它是O（V）？

我在某处遗漏了什么吗？对不起，如果这个问题太天真了。

Answer 1

表示图形的三种主要方式是：

• 邻接矩阵 - Θ(|V|²) 空间。
• 邻接表 - Θ(|V| + |E|) 空间。
• 具有指向彼此的指针的节点对象/结构的集合——这基本上只是表示邻接列表的另一种方式。Θ(|V| + |E|)。（请记住，指针也需要内存。）

由于我们在谈论最坏的情况，所有这些都减少到 Θ(|V|²)，因为这是图中的最大边数。

我猜你看错书了。他们可能不是在谈论存储图形结构本身所需的空间，而是一些图形算法所需的额外空间量。

Answer 2

如果您说的是真的，那么他们可能指的是表示图的其他方法，而不是使用邻接矩阵，并且可能正在做出边密度假设。一种方法是，对于每个顶点，只需存储指向其邻居的指针/引用列表（称为邻接列表）。这将是O(|V| + |E|)。如果我们假设|E| ~ |V|，这是我们有时会看到的假设，那么我们就有O(|V|)空间。但请注意，在最坏的情况下，|E| ~ |V|^2即使是这种表示图的方法也是O(|V|^2)在最坏的情况下。

看，这很简单；在最坏的情况下，这是无法回避的事实|E| ~ |V|^2。一般来说，E在最坏的情况下不可能有一个表示不是 O(|V|^2)。

但是，最好有一个准确的报价。这很重要。我们不想发现自己撕毁了您对正确陈述的误解。