图的实现及邻接矩阵的初始化

Question

图通常使用邻接矩阵来表示。有多种来源表明可以避免初始化成本为 |V^2|（其中V为顶点数），但我还没有想到如何实现。

在Java中，仅通过声明矩阵，例如boolean adj[][]，运行时将自动用false初始化数组，并且这将以 O(V^2) 的代价完成（即数组的维度）。

我是否误解了？是否有可能避免邻接矩阵初始化的二次成本，或者这只是一些依赖于实现语言的理论？

- Cratylus

Answer 1

使用稀疏矩阵表示邻接矩阵中仅分配“1”的位置，而不是矩阵的每个元素（其中可能包括大量的“0”），这样做是可能的。您可能会发现此主题也很有用。

- A_A

---

一个邻接矩阵的稀疏表示就是邻接表。 - Li-aung Yip

Answer 2

翻译如下： 默认初始化矩阵的值实际上是一种特性。如果没有默认初始化，你仍然需要自己初始化每个字段，以便知道它的值是什么。邻接矩阵有这样的缺点：它们在内存效率方面很差（它们需要O(n^2)个内存单元），并且正如你所说，它们的初始化速度较慢。然而，初始化从来不被认为是最大的问题。相信我，内存分配要慢得多，所需的内存比初始化时间更具限制性。

---

在许多情况下，人们更喜欢使用邻接表而不是矩阵。这样的列表需要O(m)内存，其中m是图中边的数量。这更有效率，特别是对于稀疏图。唯一比邻接矩阵表示法差的操作是查询i和j之间是否有边。矩阵可以在O(1)时间内回答，而列表肯定会慢得多。

然而，许多典型的图算法（如Dijkstra、Bellman-Ford、Prim、Tarjan、BFS和DFS）只需要迭代给定顶点的所有邻居。如果使用邻接表而不是矩阵，则所有这些算法都会受益匪浅。

- Boris Strandjev

---

那么你的意思是说，没有什么“诀窍”可以在小于二次时间内初始化数组？即使在理论上也不行？ - Cratylus

@user384706 没有，理论上也不可能有。但是，有一些函数使用高度优化的操作，比如C++的memset函数。 - Boris Strandjev

它们只在某些情况下对内存效率不佳。我知道你想表达什么，但重要的是要知道矩阵可以具有内存效率。请参见此线程以获取更多信息。 - keyser

并行算法通常比邻接表更容易将算法并行化，特别是对于简单的二维数组。请注意，您列表中列出的大多数算法都很难实现工作效率的并行化。这是一个权衡利弊的问题。 - Voo

Answer 3

这篇文章有很多混淆和错误的信息。实际上，有一种方法可以避免邻接矩阵（以及任何数组）的初始化成本。但是，由于Java原语在内部使用默认值进行初始化，因此无法使用该方法。

假设您可以创建一个未自动初始化的数组data [0..n]。首先，它将填充来自先前存储在内存中的垃圾数据。如果我们不想花费O（n）的时间来覆盖它，则需要某种方式来区分我们添加的好数据和垃圾数据。

“诀窍”是使用辅助堆栈跟踪包含良好数据的单元格。第一次写入data [i]时，我们将索引i添加到堆栈中。由于堆栈仅随着我们添加而增长，因此它永远不会包含任何我们需要担心的垃圾数据。

现在，每当我们访问data [k]时，我们可以通过扫描堆栈查找k来检查其是否为垃圾数据。但是这将需要O（n）的时间来读取每个元素，从而打破了数组的初衷！

为了解决这个问题，我们制作另一个辅助数组stack_check [0..n]，它也开始充满垃圾。该数组包含指向堆栈中元素的指针。现在，当我们第一次写入data [i]时，我们将i推送到堆栈上，并将stack_check [i]设置为指向新堆栈元素。

如果data [k]是好数据，则stack_check [k]指向保存k的堆栈元素。如果data [k]是垃圾，则stack_check [k]的垃圾值指向堆栈之外或指向除k以外的某个堆栈元素（因为从未将k放入堆栈中）。检查此属性仅需要O（1）的时间，因此我们的数组访问仍然很快。

将所有内容组合起来，我们可以通过让它们充满垃圾来在O（1）的时间内创建我们的数组和辅助结构。在每次读取和写入时，我们使用辅助程序在O（1）时间内检查给定单元格是否包含垃圾。如果我们正在覆盖垃圾，则更新辅助结构以将该单元格标记为有效数据。如果我们读取垃圾，则可以根据给定问题适当地处理它。例如，我们可以返回像0这样的默认值（现在您甚至无法告诉我们没有初始化它！）或者可能抛出异常。

- Channing Merchandise

Answer 4

我会详细解释一下A_A的答案。他建议使用稀疏矩阵，这基本上意味着你回到了维护邻接表的状态。

你有两个使用矩阵的原因——如果你根本不关心性能，喜欢它提供的简单代码，或者如果你确实关心性能，但是你的矩阵将相对填满（为了这篇文章的缘故，我们假设至少填充20%）。

显然，你确实关心性能。如果你的矩阵将相对空置，它的初始化开销可能是有意义的，最好使用邻接表。如果它将相当填满，初始化变得可以忽略——你需要填充矩阵中的正确单元格（这将比初始化更多时间），并且你需要处理它们（再次，这将比初始化花费更多时间）。

- zmbq