简单的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