¿Por qué es la complejidad temporal tanto de DFS como de BFS O (V + E)?
El algoritmo básico para BFS:
set start vertex to visited
load it into queue
while queue not empty
for each edge incident to vertex
if its not visited
load into queue
mark vertex
Así que creo que la complejidad del tiempo sería:
v1 + (incident edges) + v2 + (incident edges) + .... + vn + (incident edges)
dóndev es vértice1 an
En primer lugar, ¿es correcto lo que he dicho? En segundo lugar, ¿cómo es esto?O(N + E), y la intuición de por qué sería realmente agradable. Gracias