计算每个节点的邻居度数的总和？

Question

对于无向图中的每个节点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] 

有人可以解释什么程度[U]确实在这种情况下，如何twodegree [U] = twodegree [U] +程度[W]应该是的总和你的邻居的程度？

Answer 1

这里，degree[u]是节点u（即与其相邻的节点的数量）的程度。您可以看到第一个循环计算出的结果，该结果在图中的所有边上进行迭代，并为图中的每个边增加degree[u]。

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

希望这会有所帮助！