BFS:
La complejidad temporal es O(|V|) donde |V| es el número de nodos, debe atravesar todos los nodos.
La completitud del espacio también es O(|V|) , ya que en el peor de los casos debe mantener todos los vértices en la cola.
DFS:
- En lugar de usar una matriz y ordenar elementos de mayor a menor, ¿cómo puedo usar un montón?
- Tengo un muy buen conocimiento de C ¿Debo continuar con estructuras de datos o comenzar con C ++?
- Gráfico distribuido: ¿Cuál es la forma más efectiva de distribuir los nodos de un gráfico en diferentes servidores en un sistema distribuido?
- ¿Cuál es el mejor enfoque para mí para aprender algoritmos y estructuras de datos?
- ¿Por qué usar un diagrama de flujo es una mala práctica en la programación?
La complejidad temporal es nuevamente O(|V|) , necesita atravesar todos los nodos.
Complejidad del espacio: depende de la implementación, una implementación recursiva puede tener una complejidad de espacio O(h) [el peor de los casos], donde h es la profundidad máxima de su árbol.
Usar una solución iterativa con una pila es en realidad lo mismo que BFS, solo usar una pila en lugar de una cola, por lo que obtienes tanto O(|V|) como complejidad de tiempo y espacio.
(*) Tenga en cuenta que la complejidad del espacio y la complejidad del tiempo es un poco diferente para un árbol que para los gráficos generales porque no es necesario mantener un conjunto visited para un árbol, y |E| = O(|V|) |E| = O(|V|) , entonces el |E| El factor es en realidad redundante.
