Ejemplo simple de bfs ... No lo entiendo

Question

Estoy tratando de entender cómo funciona BFS con una cola para descubrir la ruta más corta. Supongamos que tengo una grilla:

1--2--3 
| | | 
4--5--6 
| | | 
7--8--9 
| 
0 

La mancha de inicio es '9' y el objetivo es '0'.

Entonces ... empujo el comienzo ...

push 9 {9} 
pop 9 {} 
push 6 {6} 
push 8 {6,8} 
pop 6 {8} 
push 3 {8,3} 
push 5 {8,3,5} 
pop 8 {3,5} 
push 7 {3,5,7} 
pop 3 {5,7} 
push 2 {5,7,2} 
pop 5 {7,2} 
push 4 {7,2,4} 
pop 7 {2,5} 
found 0 

¿Cómo puedo extraer la ruta más corta de este lío? No veo cómo esto me da el camino más corto. ¿Estoy pensando en eso?

Gracias!

Answer 1

Para encontrar la ruta más corta, cada nodo también debe "recordar" cómo lo alcanzó durante su BFS [qué vértice llevó a descubrirlo].

En cpp, para su ejemplo, puede usar un map<int,int> para ello.
ejemplo simple:

map[9] = -1; //indicationg source 
map[6] = 9; 
map[8] = 9; 
map[3] = 6; 
map[7] = 8 ; 
... 
map[0] = 7; 

para obtener la ruta más corta, sólo tienes que seguir el camino de 0 a la fuente [cuando el valor es -1].

Answer 2

Lo que debe hacer es recordar, para cada nodo, cómo llegó allí. Esto implica agregar un miembro de datos a cada nodo (si está utilizando estructuras o clases para representar nodos) o, de forma menos invasiva, mantener una lista paralela de enteros o punteros de nodo. Como etiquetó esto con C++, asumo que está buscando una solución C++. Algo como esto funciona:

#include <iostream> 
#include <queue> 
#include <stdexcept> 
#include <vector> 

struct graph { 

    graph(size_t nodes) 
    : m_adjacency_list(nodes) { 
    } 

    size_t number_of_nodes() const { 
    return m_adjacency_list.size(); 
    } 

    std::vector<size_t> const& neighbours_of(size_t node) const { 
    return m_adjacency_list.at(node); 
    } 

    void add_edge(size_t from, size_t to) { 
    std::vector<size_t>& al = m_adjacency_list.at(from); 
    if (to >= m_adjacency_list.size()) 
     throw std::runtime_error("Tried to add edge to non-existant node"); 
    for (size_t i = 0; i < al.size(); ++i) if (al[i] == to) return; 
    al.push_back(to); 
    } 

private: 

    std::vector<std::vector<size_t>> m_adjacency_list; 
}; 


int main() { 

    // generate your grid 
    graph g(10); 
    g.add_edge(1, 2); 
    g.add_edge(1, 4); 
    g.add_edge(2, 1); 
    g.add_edge(2, 3); 
    g.add_edge(2, 5); 
    g.add_edge(3, 2); 
    g.add_edge(3, 6); 
    g.add_edge(4, 1); 
    g.add_edge(4, 5); 
    g.add_edge(4, 7); 
    g.add_edge(5, 2); 
    g.add_edge(5, 4); 
    g.add_edge(5, 6); 
    g.add_edge(5, 8); 
    g.add_edge(6, 3); 
    g.add_edge(6, 5); 
    g.add_edge(6, 9); 
    g.add_edge(7, 4); 
    g.add_edge(7, 8); 
    g.add_edge(7, 0); 
    g.add_edge(8, 5); 
    g.add_edge(8, 7); 
    g.add_edge(8, 9); 
    g.add_edge(9, 6); 
    g.add_edge(9, 8); 
    g.add_edge(0, 7); 

    // do the bfs 
    std::vector<size_t> reached_by(g.number_of_nodes(), g.number_of_nodes()); 
    std::queue<size_t> q; 
    size_t start = 9; 
    size_t target = 0; 
    reached_by[start] = start; 
    q.push(start); 
    while (!q.empty()) { 
    size_t node = q.front(); 
    q.pop(); 
    for (size_t i = 0; i < g.neighbours_of(node).size(); ++i) { 
     size_t candidate = g.neighbours_of(node)[i]; 
     if (reached_by[candidate] == g.number_of_nodes()) { 
     reached_by[candidate] = node; 
     if (candidate == target) break; 
     q.push(candidate); 
     } 
    } 
    } 

    if (reached_by[target] == g.number_of_nodes()) 
    std::cout<<"No path to "<<target<<" found!"<<std::endl; 
    else { 
    std::cout<<"Path to "<<target<<": "; 
    for (size_t node = target; node != start; node = reached_by[node]) 
     std::cout<<node<<" <- "; 
    std::cout<<start<<std::endl; 
    } 

} 

En este código, el reached_by vector se utiliza para realizar un seguimiento de desde qué nodo se llegó a todos los nodos. Una vez que se encuentra el objetivo, puede rastrear el camino hacia atrás hasta el punto de partida utilizando ese vector.

La salida de la ejecución de este programa es

Path to 0: 0 <- 7 <- 8 <- 9