Breadth-First Search

Now that I’ve written about queues, I’ll write about breadth-first search.

Breadth-first search is a graph search algorithm. In a breadth-first search, we explore all of a vertex’s adjacent vertices before proceeding to the adjacent vertices’ adjacent vertices. Here is an outline of the algorithm:

(1) Enqueue and mark the source vertex.

(2) Dequeue a vertex. If the vertex is a match, then return the vertex. If the vertex is not a match, then enqueue and mark all of its unmarked adjacent vertices.

(3) If the queue is empty, then return nil. If the queue is not empty, then go to (2).

Breadth-first search uses a mix of two data structures: a queue and an array.

Unlike arrays, graphs are not linear. Whereas an element of an array can have only one succeeding element, a vertex in a graph can have many adjacent vertices. Consequently, we store vertices for later processing. And because we want to process a vertex before its adjacent vertices, we want to store vertices in a first-in, first-out data structure. In other words, we want to use a queue. So, we store unexplored vertices in a queue and process them as we remove them from the queue.

Breadth-first search corresponds to level-order tree traversal, which goes through the elements of a tree level by level. In fact, breadth-first search gets its name from the fact that, when it explores a tree, it explores the breadth of the tree, traversing each level before going deeper. However, breadth-first search applies to all graphs.

Because the graph doesn’t have to be a tree, it might contain cycles. So, in a breadth-first search we could come to the same vertex again. To avoid processing a vertex more than once, we mark the vertices that we’ve visited.

Here is my Ruby implementation of breadth-first search.

In my implementation, I assume that an adjacency list represents the graph.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s