algorithms undirected graph twodegree[]
- by notamathwiz
For each node u in an undirected graph, let twodegree[u] be the sum of the degrees of u's neighbors. Show how to compute the entire array of twodegree[.] values in linear time, given a graph in adjacency list format.
This is the solution
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]
can someone explain what degree[u] does in this case and how twodegree[u] = twodegree[u] + degree[w] is supposed to be the sum of the degrees of u's neighbors?