Books / Analysis of Algorithms / Chapter 16

Breadth-First Search

Now that we have reviewed the basic terminology associated with graphs, the first algorithm we will investigate is breadth-first search. This algorithm is used to find the shortest paths (by number of edges) to every reachable vertex from a given one.

Problem: Given a source vertex s, find the shortest paths (in terms of number of edges) to every reachable vertex from s.

Using breadth-first search algorithm, we will use will find all vertices reachable at a distance k before discovering reachable vertices at a distance k+1. Ultimately, the algorithm will produce a breadth-first tree with s as the root.

During the execution of the algorithm, vertices will be colored (denoted by u.color). The colors represent the vertex’s current state as follows

  • white - the vertex is undiscovered (i.e. currently no path has been found to the vertex)
  • gray - the vertex has been discovered and is on the frontier, i.e. there may be further vertices that can be discovered
  • black - the vertex has been discovered and has been completely searched

The algorithm also uses two additional fields for each vertex

u.π - predecessor vertex

u.d - distance when the vertex is first discovered (and is subsequently the shortest distance from the source)

We will employ a queue Q which will track which vertices are currently under discovery. Thus vertices that have not yet been placed in Q will be white, those that are in Q will be gray, and those that have been removed from Q will be black.

In this chapter

BFS Algorithm

The algorithm for breadth-first search is

BFS(G,s)
1.  for each vertex u ∈ G.V - {s}
2.     u.color == WHITE
3.     u.d = INF
4.     u.pi = NIL
5.  s.color = GRAY
6.  s.d = 0
7.  s.pi = NIL
8.  Q = ∅
9.  ENQUEUE(Q,s)
10. while Q ≠ ∅
11.    u = DEQUEUE(Q)
12.    for each v ∈ G.Adj[u]
13.       if v.color == WHITE
14.          v.color = GRAY
15.          v.d = u.d + 1
16.          v.pi = u
17.          ENQUEUE(Q,v)
18.    u.color = BLACK

Basically the algorithm performs the following operations:

  1. Initialize Q with the source vertex s
  2. Dequeue the head vertex u from Q and mark as black
  3. Queue all white vertices adjacent to u marking them as gray, set their distance to u’s distance + 1, and set their π to u
  4. Repeat 2-3 until Q = ∅

Analysis

Since no vertex is ever enqueued/dequeued more than once ⇒ O(V)

Each adjacency list is only scanned once (when the vertex is dequeued) with max size the total number of edges ⇒ O(E)

Initialization overhead ⇒ O(V)

Thus the total run time for BFS is

image

It can be proven that the algorithm produces the shortest paths (in terms of the minimum number of edges) to all reachable vertices from the source s. These paths can be represented by a breadth-first tree that is given by the predecessor subgraph

image

In other words, the predecessor graph contains all the vertices with predecessors that are reachable plus the source and all the predecessor edges.

Furthermore, it can be shown that since the predecessor subgraph is a tree, by theorem B.2 of CLRS

image

The predecessor tree can be traversed (using the π’s) to give the shortest path from s to v.

Example

Consider the five node (undirected) graph

image

If we select vertex 5 as the source, then d[5]=0, π[5]=/, Q={5}, thus the initialization gives

image

Iteration 1: dequeue vertex 5 and enqueue vertex 2

image

Iteration 2: dequeue vertex 2 and enqueue verticies 1,3

image

Iteration 3: dequeue vertex 1 and enqueue vertex 4

image

Iteration 4: dequeue vertex 3 and enqueue no vertices

image

Iteration 5: dequeue vertex 4 and enqueue no vertices (thus leaving the queue empty)

image

The final predecessor graph, i.e. breadth-first tree, for this BFS is

image


Licenses and Attributions


Speak Your Mind