Maze solving with breadth first search

Question

Can someone please explain how could I solve a maze using breadth first search? I need to use breadth first search to find shortest path through a maze, but I am so confused.

This is the pseudo code from my book:

void breadth_first_search(tree T) {
  queue!;
  node u, v;

  initialize(Q);
  v = root of T;
  visit v;
  enqueue(Q, v);

  while (!empty(Q)) {
    dequeue(Q, v);
    for (each child u of v) {
      visit u;
      enqueue(Q, u);
    }
  }
}

So if I have a maze that is stored in a 2D matrix, is the "root" (i.e. the starting point), going to be in maze[x][y]?

Answer 1

Short answer: Yes

Explanation:

That pseudocode is representing the path through the maze as a path to the leaf of a tree. Each spot in the maze is a node on the tree and each new spot you can go to from there is a child of that node.

In order to do breadth first search, an algorithm first has to consider all paths through the tree of length one, then length two, etc. until it reaches the end, which will cause the algorithm to stop since the end has no children, resulting in an empty queue.

The code keeps track of the nodes it needs to visit by using a queue (Q). It first sets the start of the maze to the root of the tree, visits it (checks if it is the end), then removes the root from the queue and repeats the process with each child. In this way, it visits the nodes in post-order i.e. root, (each child of root), (each child of first child), (each child of second child), etc. until it gets to the end.

Edit: As it stands, the algorithm may not terminate when it reaches the end because of other nodes after it in the queue. You will have to write the condition for termination yourself.