Simple bfs example... I don't get it

Question

I'm trying to understand how BFS works with a queue to figure out the shortest path. Let's say I have a grid:

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

Starting spot is '9' and target is '0'.

So...I push the start...

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

How can I extract the shortest path from this mess? I don't see how this gives me the shortest path. Am I thinking about it wrong?

Thanks!

Answer 1

To find the shortest path, each node should also "remember" how you reached it during your BFS [which vertex led to discovering it].

In cpp, for your example, you can use a map<int,int> for it.
Simple example:

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

To get the shortest path, just follow the path from 0 to the source [when value is -1].

Answer 2

What you need to do is to remember, for each node, how you got there. This involves either adding a data member to each node (if you are using structs or classes to represent nodes) or, less invasively, keep a parallel list of integers or node pointers. Since you tagged this with C++ I assume that you are looking for a C++ solution. Something like this works:

#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 this code the vector reached_by is used to keep track of from which node every node was reached. Once the target is found you can just trace the path backwards to the starting point using that vector.

The output of running this program is

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