Creo que hay tres formas de hacerlo sin hacer cola.
1. Use dos pilas para imitar una cola. Insertar elementos [math] n [/ math] y sacarlos de una cola tan falsa es [math] O (n) [/ math] en tiempo y espacio, como siempre fue, por lo que en realidad es una implementación de cola razonable .
2. Si realmente quiere ser confuso por alguna razón, use una pila y recursividad (donde la pila de llamadas al procedimiento toma el rol de una de las dos pilas de la solución 1). Me interesé e intenté implementarlo: creo que el siguiente pseudocódigo debería hacerlo (pero no lo he probado). No incluye código para almacenar realmente la ruta al destino. Lo usa llamando a bfs con un vértice de origen y destino.
- ¿Debo comenzar a aprender programación de computadoras con CS50 o con un libro de estructuras de datos y algoritmos?
- ¿Cuánta teoría de probabilidad necesitas para entender y aplicar algoritmos comerciales populares?
- ¿De dónde viene la palabra algoritmo?
- Cómo convertir de binario a decimal
- ¿Cuáles son algunos algoritmos de redes neuronales artificiales?
bfs = función (src, dst)
crear pila S
empuje src hacia S
mientras que S no está vacío
bfs_recurse (S, dst)
terminar mientras
función final
bfs_recurse = función (S, dst)
si S está vacío, devuelve falso
pop un vértice v de S
si bfs_recurse (S, dst) entonces devuelve verdadero
si v es igual a dst, entonces devuelve verdadero
para w en vecinos (v) hacer
si w no se descubre entonces
etiqueta w como descubierta
presione w sobre S
terminara si
fin para
función final
La complejidad del tiempo sigue siendo la misma de siempre.
3. La tercera forma es utilizar la primera búsqueda en profundidad con profundización iterativa. Es decir, primero realiza una búsqueda profunda pero con un límite en la longitud de la ruta, y aumenta el límite paso a paso. Eso parece muy derrochador, pero dependiendo del gráfico (por ejemplo, si el gráfico es un árbol), la complejidad del tiempo puede ser igual a lo que solía ser. También podría ser mucho peor, por ejemplo, si el gráfico es una secuencia lineal de nodos, entonces la complejidad del tiempo aumenta de [matemática] O (n) [/ matemática] a [matemática] O (n ^ 2) [/ matemática] . Por otra parte, existe la ventaja de que realmente no utiliza una cola, ni siquiera una falsa, y además utiliza mucha menos memoria en la búsqueda.
