Se garantiza que BFS encontrará la ruta más corta entre el nodo inicial y todos los nodos que visita (si esa ruta existe). Por lo tanto, el nodo de inicio debe ser uno de los nodos entre los que desea encontrar la ruta más corta. Llamemos al otro punto final de la ruta ‘nodo final’.
El código de la descripción necesita solo una pequeña modificación … en lugar de establecer visit [u] en 1, configúrelo en el índice del nodo desde el que lo visitó. Esto es para poder reconstruir el camino. Además, puede detenerse después de llegar al otro punto final de la ruta, por lo que debe pasarse como un parámetro y verificarse al visitar un nuevo nodo; esto no es absolutamente necesario.
Finalmente, deberá agregar un bloque para reconstruir la ruta desde la matriz de visitas, donde almacenamos los índices de los predecesores. Comenzando desde el nodo final, volvemos al nodo de inicio:
- Cómo cortar un árbol con una motosierra
- Cómo entender el algoritmo maestro del documento sobre la resolución del isomorfismo gráfico en tiempo cuasi polinomial
- ¿Hay algún libro sobre estructuras de datos y algoritmos que se centre más en la perspectiva de gestión de memoria de los algoritmos?
- ¿Cuáles son algunos algoritmos que usamos diariamente que tienen complejidades [matemáticas] O (n), O (n ^ 2), [/ matemáticas] y [matemáticas] O (\ log n) [/ matemáticas]?
- ¿Cuál sería el impacto económico de un algoritmo de compresión tan eficiente como el representado en Silicon Valley?
path.prepend (visita [endnode]);
while (visit [path.last ()]! = startnode) {
path.prepend (visita [path.last ()]);
}
