4

我需要计算其值由以下无效的伪 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)。

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

编辑：更多信息

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

3 回答 3

5

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

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

根据@Patrick 的建议，让我们使用A^2，看看如何有效地更新它，而无需每次都从头开始重新计算。 是从到A^2_ij的长度为 2 的路径的数量，请记住，它也会有对角线条目，因为从顶点到自身总是有长度为 2 的路径。如果你有，你可以很容易地计算第二个邻居的数量，所以让我们在图形发生变化时保持所有更新在内存中。ijA^2A^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。事实证明，row iofBA是 row jof A，row jofBA是 row iof A，其余为零。再说一次，计算速度很快。

删除边缘将是相似的。

您只需要计算A^2第二个邻居的数量，因此无需计算每一步有多少非零非对角线条目，通过一些额外的工作，您可以通过A^2添加时非零条目的数量变化来计算AB + BA.

编辑

整个事情用另一种语言解释：

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

于 2011-07-13T09:36:06.383 回答
1

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

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

于 2011-07-12T15:44:04.647 回答
0

获取节点的邻居列表 (node_main)。拜访每个邻居。将它的每个邻居添加到邻居列表中，除非它是 node_main 的邻居之一（或者是 node_main 本身）。我错过了什么吗？

于 2011-07-12T15:51:30.363 回答