Ví dụ bfs đơn giản ... Tôi không nhận được nó

Question

Tôi đang cố gắng hiểu cách BFS hoạt động với hàng đợi để tìm ra đường đi ngắn nhất. Giả sử tôi có lưới:

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

Vị trí bắt đầu là '9' và mục tiêu là '0'.

Vì vậy ... Tôi đẩy đầu ...

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 

Làm thế nào tôi có thể trích xuất các đường đi ngắn nhất từ ​​đống lộn xộn này? Tôi không thấy cách này mang lại cho tôi con đường ngắn nhất. Tôi đang nghĩ về nó sai?

Cảm ơn!

Answer 1

Để tìm đường đi ngắn nhất, mỗi nút cũng nên "ghi nhớ" cách bạn đạt đến nó trong BFS của bạn [mà đỉnh dẫn đến khám phá nó].

Trong cpp, ví dụ của bạn, bạn có thể sử dụng map<int,int> cho nó.
đơn giản ví dụ:

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

Để có được con đường ngắn nhất, chỉ cần làm theo con đường từ 0 đến nguồn [khi giá trị là -1].

Answer 2

Điều bạn cần làm là ghi nhớ, đối với mỗi nút, cách bạn đến đó. Điều này liên quan đến việc thêm một thành viên dữ liệu vào mỗi nút (nếu bạn đang sử dụng các cấu trúc hoặc các lớp để biểu diễn các nút) hoặc ít xâm lấn hơn, hãy giữ một danh sách song song các số nguyên hoặc nút con trỏ. Kể từ khi bạn gắn thẻ này với C + +, tôi giả định rằng bạn đang tìm kiếm một giải pháp C++. Một cái gì đó như thế này hoạt động:

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

} 

Trong mã này, vectơ reach_by được sử dụng để theo dõi từ nút nào đã đạt đến. Khi mục tiêu được tìm thấy, bạn có thể chỉ cần theo dõi đường dẫn ngược về điểm bắt đầu sử dụng vectơ đó.

Kết quả chạy chương trình này là

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