在图形中获取下一个最近邻居节点的最佳方法是什么？

Question

我需要计算一个值，该值由以下低效的伪Python代码给出：

def foo(a,b):
   tmp = 0
   for i in graph.nodes():
       for j in graph.nodes():
          tmp += c
          if (i and j are neighbors):
              tmp += a - c
          elif (i and j are next-neighbors):
              tmp += b - c
   return tmp

换句话说，给定所有节点对，foo = a *（E = 边数）+ b *（EE = 不相邻但有共同邻居的节点对数）+ c *（N（N-1）/ 2-EE-E）。

我尝试了一些广度优先搜索，但没成功。

编辑：更多信息

• 图不是静态的。我不断添加和删除边缘，因此不能仅计算一次。我必须不断更新“下一个邻居列表”。
• 我将图存储为邻接矩阵。

- Rafael S. Calsaverini

---

图形是如何存储的？ - Patrick

顶点数是固定的吗？ - Szabolcs

是的，我保持顶点数量不变。感谢您提供的出色答案。 - Rafael S. Calsaverini

Answer 1

这是一个大致的想法。但首先，有一些假设：1.无向图2.顶点数恒定。

您的图形不断变化。因此，您需要高效地更新邻居（边缘）和第二邻居的数量。第一个很简单，所以让我们看看第二个邻居。

根据@Patrick的建议，让我们使用A²，并看看如何在不每次重新计算它的情况下有效地更新它。A²ij是从i到j的长度为2的路径数，请记住它也会有对角线条目，因为总是有从顶点到自身的长度为2的路径。如果您拥有A²，则可以轻松计算第二邻居的数量，因此让我们在图形更改时将所有A²保持更新在内存中。

如何有效地更新A²：

当您添加/删除边缘时，您通过仅具有两个条目的矩阵B更改A。假设我们正在添加（而不是删除）边缘。然后(A+B)²=A²+AB+BA+B²。

假设添加的边缘是(i,j)。

B²很简单：(B²)ii=(B²)jj=1，其余为0。

AB=transpose(BA)，因此我们只需要计算其中之一，例如BA。事实证明，BA的第i行是A的第j行，BA的第j行是A的第i行，其余为零。因此，它也很快。

删除边缘将类似。

您只需要第二邻居的计数，因此，与其在每个步骤中计算A²具有非零非对角线条目的数量，不如通过一些额外的工作，在添加AB+BA时计算A²中非零条目的数量变化量。

编辑

这整个过程用另一种语言解释：

让我们追踪矩阵 M 中任意两个顶点之间长度为2的路径数量。当我们在i和j之间添加（删除）一条边时，i和j以及所有邻居之间的长度为2的路径数量都会增加（减少）1，因此可以在每次更改图形后轻松地使用O(n)时间更新M。

- Szabolcs

---

太好了！这正是我所需要的。谢谢。每次更改图形时进行O(N)更新，使我可以进行O(1)查找！！！完美。 - Rafael S. Calsaverini

Answer 2

如果你将图存储在邻接矩阵A中，你可以通过将矩阵与自身相乘（A^2）来找到所有长度为2的路径，如果这是你所问的。

这将花费O(n^3)的时间进行预处理，但然后你可以在常数时间内执行邻居和“下一个邻居”的查找。

- Patrick

---

问题在于我的图不是静态的。我不断地添加和删除边缘。 - Rafael S. Calsaverini

请注意，一个节点的路径长度也包括到自身的距离（例如 1 -> 2 -> 1），因此如果您使用方阵来计算下一个邻居，则需要进行更正。 - Szabolcs

“长度为两个的路径”，我的意思是，打错了。 - Szabolcs

要找到顶点i的下一个邻居数，我会计算A^2的第i行上非零条目的数量并减去1。对吗？ - Rafael S. Calsaverini

@Rafael 是的，那应该可以。为了确保，我会在计数时忽略 (i, i) 这个条目，因为如果这是一个没有长度为二的路径到自身的有向图，你可能会纠正不存在的错误。 - Patrick

Answer 3

获取与您的节点（node_main）相邻的节点列表。访问每个邻居。将其每个邻居添加到邻居的邻居列表中，除非它是node_main的邻居（或者是node_main本身）。我有遗漏什么吗？

- Stephen C

---

我的图是一个邻接矩阵。这将是O(N^2)。我想也许有一种O(N.log(N))的方法来做到这一点。如果我这样做，我会访问每对邻居两次，以及每对下一个邻居超过两次，我相信。 - Rafael S. Calsaverini

请原谅我，我的图论知识已经有10年了。获取当前邻居列表并访问每个邻居（一次）似乎很简单，就像进行任何广度优先搜索一样。从那里开始，您只需检查该节点的邻居是否在您的邻居列表中，其中包括您正在计算的原始节点。您还可以访问每个邻居并将其所有邻居添加到列表中。使结果列表唯一并删除主节点及其直接邻居，即可获得列表。性能由连接性确定，其中完全连接的图是最坏情况，仍为O（N ^ 2），对吗？ - Stephen C

但如果我使用邻接矩阵，就必须始终检查所有节点以确定邻居列表，因此获取邻居始终是O（N），而邻居的邻居始终是O（N ^ 2），无论图的连通性如何。我想我被卡在了O（N ^ 2）上。 :( - Rafael S. Calsaverini