Realmente no hay suficientes datos para responder: depende de las propiedades estructurales de la estructura de datos en la que estamos buscando.
Sin más información, podemos decir que no se debe visitar ningún nodo (vértice) ni borde más de una vez, en adelante O (| V | + | E |).
El borde | E | No se debe olvidar el término porque en algunos casos (como gráficos altamente conectados) puede ser mucho mayor que el número de nodos. En un árbol podemos ignorarlo.
- ¿Qué estrategia emplearías para vencer a un algoritmo de computadora jugando póquer matemáticamente perfecto?
- ¿Se puede implementar una lista vinculada individualmente como una lista doblemente vinculada?
- Cómo mostrar que la distancia más corta entre 2 curvas que no se cruzan siempre se encuentra a lo largo de su normal común
- ¿Cómo resolvemos el problema B, 'Can of Worms', del Chicago Invitational Programming Contest 2013?
- ¿Existe una versión del problema de la mochila en la que haya una restricción sobre qué objetos se pueden colocar en la bolsa?
Búsqueda de amplitud primero – Wikipedia
Tenga en cuenta que si usa BFS en un gráfico, necesita una forma de romper bucles, o el algoritmo será incorrecto. Una forma de hacerlo es almacenar los estados visitados o marcarlos. Si no tiene forma de romper los bucles, la respuesta no debe ser sobre la complejidad sino sobre la corrección del algoritmo.
No hay problemas para los árboles, pero aún tiene que almacenar futuros nodos para visitar, ese es el principio del algoritmo BFS. Me pregunto de dónde viene su restricción “sin almacenar los estados visitados”. Parece muy poco BFS, ya que generalmente BFS se usa en contextos donde la complejidad del espacio O (| V |) no es un problema.
