CODEWITHSUNDEEP
algorithmgraphpseudocode
notamathwiz
notamathwiz

Reputation: 235

Counting the sum of every nodes' neighbors' degrees?

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?

Upvotes: 0

Views: 7083

Answers (2)

Oleg Melnikov
Oleg Melnikov

Reputation: 3298

In addition to what @templatetypedef has said, the statement twodegree[u] = twodegree[u] + degree[w] simply keeps track of the twodegree of u while it keeps iteratively (or cumulatively) adding the degrees of its neighbors (that are temporarily stored in w)

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372982

Here, degree[u] is the degree of the node u (that is, the number of nodes adjacent to it). You can see this computed by the first loop, which iterates over all edges in the graph and increments degree[u] for each edge in the graph.

The second loop then iterates over every node in the graph and computes the sum of all its neighbors' degrees. It uses the fact that degree[u] is precomputed in order to run in O(m + n) time.

Hope this helps!

Upvotes: 4

Related Questions