¿Cuál puede ser la complejidad del tiempo de un algoritmo que calcula los pesos de los nodos en un gráfico?
-
29-09-2020 - |
Pregunta
Estoy tratando de encontrar la mejor complejidad del tiempo de un algoritmo que calcula los pesos de todos los nodos en un gráfico.El peso del nodo se define como la suma de los pesos de los bordes adyacentes a él.Puedo argumentar que el algoritmo es similar al que calcularía el grado de todos los nodos y que ciertamente se necesita O (| V | + | E |), pero podemos decir lo mismo si estamos tratando de calcular los pesos denodos?
Solución
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)
Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange