Queues Continued

Breadth First Search

One common algorithm that is implemented using a queue is breadth-first search or BFS. BFS can be used for many different search problems, including with graphs, which we will discuss later in the semester.

Imagine for now that we have a rectangular maze consisting of either walls or empty space. We want to go from the start of the maze which is the upper left corner, to the end which is the bottom right.

In a program, we can represent such a maze with an array of Strings, like so:


String[] mazeString = {
    "-#################",
    "----------##-----#",
    "-########-##-##-##",
    "-########----##-##",
    "-########-#####-##",
    "-----####-#####-##",
    "#########-###---##",
    "####------#####---"};

To get from the start to the end, we will start at the start location, and explore out from there until we reach the end location.

In order to keep track of where we need to go next, BFS uses a queue. Locations that we need to visit are enqueued and then when we need to move, we dequeue a position and go there.

In order to avoid going back to the same place multiple times, we need to mark the locations that we have already visited. Pseudocode for this algorithm is:

Set current to the start position.
While current is not the end position:
1. Mark current as visited.
2. If we can go left, enqueue left.
3. If we can go right, enqueue right.
4. If we can go up, enqueue up.
5. If we can go down, enqueue down.
6. If the queue is empty, there is no path!
7. Set current to dequeue( ).
We made it!

This example shows how BFS can be used to solve the maze given above.

Breadth-first search is called "breadth-first" because it does a broad scan. It checks multiple paths step by step rather than going fully down one path. For example, when we get to the fork at (0, 1), BFS will follow both paths by looking at (1, 1) then (0, 2) then (2, 1) then (0, 3) and so on. It works this way because the queue stores the places in the order we get to them.

Depth First Search

An alternative way to solve this maze is using depth-first search, DFS. This works almost exactly the same way as BFS, except that instead of using a queue to hold the locations to search, we use a stack instead.

When we use a stack, we will visit the locations in the maze in a different order. This example shows DFS in action.

This algorithm is called "depth-first" because it follows each path as far as it can before leaving it. For example, when we get to the fork at (0, 1), DFS will follow the downward path until it reaches a dead end before returning back up to (1, 1). If we had rearranged the pushes so that down came before right, DFS would never have gone down that path at all.

Priority Queues

For some applications, we want to handle things roughly in order but may have some exceptions. For example, in an operating system scheduler, processes are given time on the CPU roughly in order, but some high priority processes can preempt others.

A queue that keeps some notion of priority in this manner is called a priority queue.

There is a search algorithm based on a priority-queue called A*, which we will look at later in the semester.

There are several ways to implement priority queues. One is to have a priority along with each object. Then on a dequeue, you would scan through looking for the highest priority item and remove it. This is clearly slower than a normal dequeue operation. Another way is to maintain separate queues for each priority level. We will see other solutions for this problem later in the semester.