What can be the time complexity of an algorithm that calculates the weights of the nodes in a graph?
-
29-09-2020 - |
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?
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