0

对于无向图中的每个节点 u，令 twodegree[u] 为 u 的邻居的度数之和。给定邻接表格式的图形，展示如何在线性时间内计算整个 twodegree[.] 值数组。

这是解决方案

for all u ∈  V :
  degree[u] = 0
  for all (u; w) ∈  E:
    degree[u] = degree[u] + 1
for all u ∈  V :
  twodegree[u] = 0
  for all (u; w) ∈  E:
    twodegree[u] = twodegree[u] + degree[w]

有人可以解释一下 degree[u] 在这种情况下的作用以及 twodegree[u] = twodegree[u] + degree[w] 应该是 u 邻居度数的总和吗？

4

2 回答 2

4

这里，degree[u]是节点的度数u（即与其相邻的节点数）。您可以看到这是由第一个循环计算得出的，该循环遍历图中的所有边并为图degree[u]中的每条边递增。

然后第二个循环遍历图中的每个节点并计算其所有邻居度数的总和。它使用预先计算的事实，degree[u]以便在 O(m + n) 时间内运行。

希望这可以帮助！

于 2013-11-01T03:41:21.593 回答
0

除了@templatetypedef 所说的之外，该语句twodegree[u] = twodegree[u] + degree[w]仅跟踪twodegree ofu而它保持迭代（或累积）添加其邻居的度数（临时存储在w）

于 2019-06-25T06:08:57.947 回答