Breadth-First Search

Breadth-First Search

a WimpyPoint presentation owned by Mark Dettinger

How to find your way out of a maze


  0         1         2         3
  0123456789012345678901234567890123456
0 #################################E###
1 ###....#.....#......###...#...#...#.#
2 #...##...###...####.....#..##.#.##..#
3 #.#########.###....##.####.##.#.#..##
4 #.............##.######..#......#...#
5 #####.#####.#..........#.##########.#
6 #S..........###.#.#.##..............#
7 #####################################
    
    
    
    

Goals


Our goal is to develop a program that answers the following three questions (ordered by increasing difficulty):
  1. Is the exit reachable from the start? (Yes or No)
  2. How many steps does it take to reach the exit on a shortest path?
  3. Output a shortest path from the start to the exit.

    
    
    
    

Reachability of the exit field


We see the problem as a graph problem: Each empty field ('S', 'E', and '.') is a vertex. Each pair of adjacent vertices is connected by an undirected edge. We will solve the problem by breadth-first search.

Since the graph is already implicitly given by the character matrix of the maze, the only additional data structure we need is a color matrix:

int color[num_rows][num_columns];
In the beginning, all vertices are colored white. We will color them gray when we enqueue them, and black when we dequeue them.
for row from 0 to num_rows-1 {
  for column from 0 to num_columns-1 {
    color[row][column] = white;
  }
}
We initialize the queue with the start field.
q = new queue();
q.enqueue(start_row,start_column);
color[start_row][start_column] = gray;
Now -- while the queue is not empty -- we run the loop of the breadth-first search.
while (q.head != q.tail) {
  v = q.dequeue();
  color[v.row][v.column] = black;
  for each (r,c) adjacent to (row,column) {
    if (maze[r][c]!='#' && color[r][c]==white) {
      q.enqueue(r,c);
      color[r][c] = gray;
    }
  }
}
After the loop has finished, all nodes reachable from the start are black. The unreachable nodes are still white.
switch (color[exit_row][exit_column]) {
  case white: 
    print("Exit is unreachable");
    break;
  case black: 
    print("Exit is reachable");
    break;
}

    
    
    
    

Computing Distances


We need another matrix to store distances.
int distance[num_rows][cum_columns];
for row from 0 to num_rows-1 {
  for column from 0 to num_columns-1 {
    color[row][column] = white;
    distance[row][column] = MAXINT;
  }
}
q = new queue();
q.enqueue(start_row,start_column);
color[start_row][start_column] = gray;
distance[start_row][start_column] = 0;
while (q.head != q.tail) {
  v = q.dequeue();
  color[v.row][v.column] = black;
  for each (r,c) adjacent to (row,column) {
    if (maze[r][c]!='#' && color[r][c]==white) {
      q.enqueue(r,c);
      color[r][c] = gray;
      distance[r][c] = distance[row][column] + 1;
    }
  }
}
switch (color[exit_row][exit_column]) {
  case white: 
    print("Exit is unreachable.");
    break;
  case black: 
    print("Exit is reachable in "+distance[exit_row][exit_column+" steps");
    break;
}

    
    
    
    

Computing the Shortest Path


We need another array to store the predecessor of each node.
vertex pred[num_rows][num_columns];
The start node has no predecessor. For all other nodes, the predecessor is set when the node is enqueued.
for row from 0 to num_rows-1 {
  for column from 0 to num_columns-1 {
    color[row][column] = white;
    distance[row][column] = MAXINT;
  }
}
q = new queue();
q.enqueue(start_row,start_column);
color[start_row][start_column] = gray;
distance[start_row][start_column] = 0;
pred[start_row][start_column] = null;
while (q.head != q.tail) {
  v = q.dequeue();
  color[v.row][v.column] = black;
  for each (r,c) adjacent to (row,column) {
    if (maze[r][c]!='#' && color[r][c]==white) {
      q.enqueue(r,c);
      color[r][c] = gray;
      distance[r][c] = distance[row][column] + 1;
      pred[r][c] = vertex(row,column);
    }
  }
}
switch (color[exit_row][exit_column]) {
  case white: 
    print("Exit is unreachable.");
    break;
  case black: 
    print("Exit is reachable in "+distance[exit_row][exit_column]+" steps: ");
    print_path_to(exit_row,exit_column);
    break;
}
In the end, the array pred provides enough information to reconstruct the path.
print_path_to (r,c) {
  if (pred[r][c]!=null) {
    print_path_to(pred[r][c].row,pred[r][c].column);
  } 
  print("("+r+","+c+")");
}

    
    
    
    

What if edges have different lengths?


for row from 0 to num_rows-1 {
  for column from 0 to num_columns-1 {
    color[row][column] = white;
    distance[row][column] = MAXINT;
  }
}
q = new PriorityQueue();
q.enqueue(start_row,start_column);
color[start_row][start_column] = gray;
distance[start_row][start_column] = 0;
pred[start_row][start_column] = null;
while (q.head != q.tail) {
  v = q.dequeue();
  color[v.row][v.column] = black;
  for each (r,c) adjacent to (row,column) {
    if (maze[r][c]!='#' && color[r][c]!=black) {
      d = distance[row][column] + edge_length[row][column][r][c];
      if (color[r][c]==white) {
        q.enqueue(r,c);
        color[r][c] = gray;
        distance[r][c] = d;
        pred[r][c] = vertex(row,column);
      }
      if (color[r][c]==gray && d < distance[r][c]) { 
        distance[r][c] = d;
        push up vertex (r,c) in priority queue;
        pred[r][c] = vertex(row,column);
      }
    }
  }
}
    
    
    
    

What if the maze is 3-dimensional?


    
    
    
    

Why don't we use depth-first search?


    
    
    
    

Hoppers


###################
#.....#############
#..##.#############
#..##.#############
#..##.#############
#S.##............E#
###################
    
    
    
    

It's just another graph problem!


    
    
    
    

Rubik's Cube


    
    
    
    

Last modified 2001-02-12


mdettinger@arsdigita.com