java - 邻接矩阵的图实现和初始化

Question

图通常使用邻接矩阵来表示。各种来源表明可以避免初始化成本为 |V^2| （V是顶点数）但我可能还没有弄清楚如何。

在 Java 中，只需声明矩阵，例如boolean adj [][]，运行时将自动初始化数组，false这将以O(V^2)为代价（数组的维度）。
我误解了吗？是否可以避免邻接矩阵初始化的二次成本，或者这只是取决于实现语言的理论？

Answer 1

矩阵值的默认初始化实际上是一个特性。如果不是使用默认初始化，您是否还需要自己初始化每个字段，以便您知道它的值是什么？

邻接矩阵有这个缺点：它们在内存效率方面很差（它们需要 O(n ² ) 内存单元），并且正如您所说，它们的初始化速度较慢。然而，初始化从未被认为是最大的问题。相信我，内存分配要慢得多，所需的内存比初始化时间更受限制。

---

在许多情况下，人们更喜欢使用邻接列表，而不是矩阵。这样的列表需要O(m)内存，其中m是图中的边数。这更有效，尤其是对于稀疏图。这个图表示比邻接矩阵差的唯一操作是查询is there edge between vertices i and j。矩阵O(1)及时回答，列表肯定会慢很多。

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

Answer 2

这可以通过使用邻接矩阵的稀疏矩阵表示来实现，其中仅分配“1”的位置，而不是矩阵的每个元素（可能包括大量的零）。您可能会发现此线程也很有用

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 这样的默认值（现在你甚至不能说我们没有初始化它！）或者可能抛出一个异常。

Answer 4

我将详细说明 A_A 的答案。他建议使用稀疏矩阵，这基本上意味着您要重新维护邻接列表。

您有两个理由使用矩阵 - 如果您根本不关心性能并且喜欢它提供的简单代码，或者如果您确实关心性能但您的矩阵将相对完整（假设至少 20%完整的，为了这篇文章）。

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