Question

I am trying to find the best time complexity of an algorithm that calculates the weights of all the nodes on a graph. The weight of the node is defined as the sum of the weights of the edges adjacent to it. I can argue that the algorithm is similar to the one which would calculate the degree of all the nodes and that certainly takes O(|V|+|E|) but can we say the same thing if we are trying to calculate the weights of nodes?

Was it helpful?

Solution

for i in V:
    weight(i) = 0
for e=(i,j) in E:
    weight(i) = weight(i) + weight(e)
    weight(j) = weight(j) + weight(e)
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top