簡單的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