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

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).

我试图考虑某种广度优先搜索，但我做不到。

编辑:更多信息

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

Answer 1

这是一个粗略的想法。但首先，一些假设:1. 无向图 2. 常量顶点数

您的图表不断变化。因此，您需要有效地更新邻居(边)和第二邻居的数量。第一个是微不足道的，所以让我们看看第二个邻居。

根据@Patrick 的建议，让我们使用 A^2 ，让我们看看如何有效地更新它而无需每次都从头开始重新计算。 A^2_ij是来自 i 的两条长度路径的数量至 j ，请记住它也会有对角线条目，因为从顶点到它本身总是有一条长度为二的路径。如果你有 A^2 , 你可以很容易地计算出第二邻居的数量，所以让我们保留所有 A^2当图形改变时在内存中更新。

如何更新A^2高效:

当你添加/删除一条边时，你改变了A通过矩阵 B只有两个条目。假设我们要添加(而不是删除)一条边。那么(A+B)^2 = A^2 + AB + BA + B^2 .

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

• B^2是微不足道的:(B^2)_ii = (B^2)_jj = 1 ，其余为0。
• AB = transpose(BA)所以我们只需要计算两者之一，比如 BA .原来那行i的 BA是行j的 A和行 j的 BA是行i的 A ，其余为零。同样，它的计算速度很快。

删除边缘将是类似的。

您只需要第二个邻居的计数，而不是计算有多少非零非对角线条目 A^2在每个步骤中，通过一些额外的工作，您可以计算出 A^2 中非零条目的数量发生了多少变化。当你添加 AB + BA .

编辑

这整件事用不同的语言解释:

让我们跟踪矩阵中任意两个顶点之间的长度为二的路径的数量 M .当我们在 i 之间添加(删除)一条边时和 j ，长度-两条路径的数量将在i之间增加(减少)一个和j的所有邻居以及j和i的所有邻居, 所以 M在 O(n) 中很容易更新图表每次更改后的时间。