Esempio bfs semplice ... Non capisco

Question

Sto cercando di capire come BFS funziona con una coda per capire il percorso più breve. Diciamo che ho una griglia:

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

Il punto di partenza è '9' e l'obiettivo è '0'.

Quindi ... spingo l'inizio ...

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 

Come posso estrarre il percorso più breve da questo pasticcio? Non vedo come questo mi dia il percorso più breve. Ci sto pensando male?

Grazie!

Answer 1

Per trovare il percorso più breve, ogni nodo dovrebbe anche "ricordare" come l'hai raggiunto durante il tuo BFS [che il vertice ha portato a scoprirlo].

In cpp, per l'esempio, è possibile utilizzare uno map<int,int> per esso.
semplice esempio:

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

per ottenere il percorso più breve, basta seguire il percorso da 0 alla sorgente [quando il valore è -1].

Answer 2

Quello che devi fare è ricordare, per ogni nodo, come ci sei arrivato. Ciò comporta l'aggiunta di un membro dati a ciascun nodo (se si utilizzano le strutture o le classi per rappresentare i nodi) o, in modo meno invasivo, mantenere un elenco parallelo di numeri interi o puntatori di nodi. Dal momento che l'hai taggato con C++, suppongo che tu stia cercando una soluzione C++. Qualcosa di simile funziona:

#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; 
    } 

} 

In questo codice il vettore reached_by viene utilizzato per tenere traccia di quale nodo è stato raggiunto ogni nodo. Una volta trovato il bersaglio, puoi tracciare il percorso all'indietro fino al punto di partenza usando quel vettore.

L'output di esecuzione di questo programma è

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