Простой пример bfs ... Я не понимаю

Question

Я пытаюсь понять, как BFS работает с очередью, чтобы выяснить кратчайший путь. Предположим, у меня есть сетка:

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

Начальная точка - 9, а цель - «0».

... Так я нажимаю старт ...

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 

Как я могу извлечь кратчайший путь из этого беспорядка? Я не понимаю, как это дает мне кратчайший путь. Я думаю об этом неправильно?

Спасибо!

Answer 1

Чтобы найти кратчайший путь, каждый узел должен также «запомнить», как вы достигли его во время BFS [эта вершина привела к его обнаружению].

В cpp для вашего примера вы можете использовать для этого map<int,int>.
Простой пример:

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

Чтобы получить самый короткий путь, просто следовать по пути от 0 до источника [когда значение равно -1].

Answer 2

Что вам нужно сделать, так это помнить, для каждого узла, как вы туда попали. Это включает либо добавление члена данных к каждому узлу (если вы используете структуры или классы для представления узлов), либо, менее инвазивно, сохранять параллельный список целых чисел или указателей узлов. Поскольку вы отметили это с помощью C++, я предполагаю, что вы ищете решение на C++. Что-то вроде это работает:

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

} 

В этом коде вектор reached_by используется для отслеживания от того, какой узел был достигнут каждый узел. Как только цель найдена, вы можете просто проследить путь назад до начальной точки с помощью этого вектора.

Выход запуска этой программы

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