图形数据结构的最坏情况记忆

Question

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

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

Answer 1

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

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

由于我们说的是最坏的情况,所有这些都减少到Θ(| V |²),因为这是图中最大边数.

我猜你误读了这本书.他们可能没有谈论存储图形结构本身所需的空间,而是谈论某些图形算法所需的额外空间量.