Después de indagar en diferentes repositorios y foros de internet al terminar nos hemos encontrado la resolución que te compartimos a continuación.
Solución:
En ambos casos, el tiempo de ejecución depende de cuánto se tarde en recorrer los bordes salientes de un nodo determinado. Con una lista de adyacencia, el tiempo de ejecución es directamente proporcional al número de aristas salientes. Dado que cada nodo se visita una vez, el costo es el número de nodos más el número de aristas, que es O(m + n). Con una matriz de adyacencia, el tiempo requerido para encontrar todos los bordes salientes es O(n) porque se deben inspeccionar todas las n columnas en la fila de un nodo. Resumiendo en todos los n nodos, esto resulta en O(n2).
¡Espero que esto ayude!
La complejidad del tiempo para DFS y BFS se puede calcular de la siguiente manera:
Iterando cada vértice una vez y sus correspondientes aristas incidentespor lo que la complejidad temporal total será ->
Complejidad de tiempo = v1 + (incident_edges en v1) + v2 + (incident_edges en v2) + …… + vn + (incident_edges en vn)
Ahora esto se puede reagrupar como -> (v1+v2+v3+…..vn) + (incident_edges en v1 + incident_edges en v2 + ….. incident_edges en vn)
Por lo tanto, la complejidad del tiempo total resultaría ser = (v1+v2+v3+…..vn) + (incident_edges en v1 + incident_edges en v2 + ….. incident_edges en vn)
(v1 + v2 + … + vn) = V o n (Número total de vértices)
Para representación de lista de adyacencia :
(bordes_incidentes en v1 + bordes_incidentes en v2 + ….. bordes_incidentes en vn) = E(Número total de bordes)
Por lo tanto, para la representación de la lista de adyacencia, la complejidad del tiempo será O (V + E)
Para representación de matriz de adyacencia :
Para visitar los vecinos del nodo correspondiente (Fila), necesitamos iterar todas las columnas para la fila en particular que equivale a V
Entonces, (bordes_incidentes en v1 + bordes_incidentes en v2 + ….. bordes_incidentes en vn) = V + V + …. V-ésima vez V) = V*V
Por lo tanto, la complejidad del tiempo será O(V + V^2) = O(V^2)
Puedes añadir valor a nuestra información añadiendo tu experiencia en los comentarios.