Breadth-First Search on Graphs

Print

Searching On Graphs

Many times, when given a graph, one might have to find whether a specific vertex is reachable from another. Or, to explore all vertices that are reachable from a start vertex (possible with an additional constraint such as limiting the maximum distance to a certain value). These are all search problems on a graph, and techniques for searching graphs lie at the heart of the field of graph algorithms. Many algorithms on graphs start out by searching their input graph to obtain structural information about the graph.

Searching a graph means systematically following the edges of the graph so as to visit the vertices of the graph.

What is Breadth-First Search?

Breadth-First Search (BFS) is one of the most basic algorithms for searching a graph and constitutes the building-block of many important graph algorithms. As stated above, Breadth-First Search is a method for finding all vertices reachable from a given start vertex, s.

One way to think about BFS is to imagine a wave starting out at the start vertex, s. The wave propagates outwards and it first hits all vertices 1 edge away from s. Then the wave hits all vertices 2 edges away, and so on. The "wave-front" then is made up of all the vertices that have been hit but not yet passed. The wave is said to pass a vertex only after it hits all of the vertices 1 edge away from it.

In order to implement the algorithm we will need a way of keeping track of two things:

  1. which vertices have been hit
  2. which vertices are in the wave-front

We can accomplish the first by somehow marking vertices that are hit. Either by setting a property of the vertex, or by keeping an array of flags for each vertex and setting the flag once a vertex is hit.

In order to accomplish the second, we will use a Queue data structure. A vertex will be enqueued when it is hit by the wave, if it hasn't been hit already. And it will be dequeued when the wave-front starts to propagate away from it (when it is about to leave the vertex).

A pseudo-code implementation of BFS is:

  1. for each vertex u in G
  2.         u.color := WHITE
  3.         u.d := ꝏ
  4.         u.π := NULL
  5. s.color := GRAY
  6. s.d := 0
  7. create empty queue Q
  8. Q.ENQUEUE(s)
  9. while not Q.empty
  10.       u := Q.dequeue
  11.       for each v in G.adj [u]
  12.             if v.color == WHITE
  13.                   v.color := GRAY
  14.                   v.d := u.d + 1
  15.                   v.π := u
  16.                   Q.ENQUEUE(v)
  17.       u.color := BLACK

Run-time Complexity of the Breadth-First Search Algorithm

The total running time of the standard Breadth-First Search algorithm is O(V+E). What that means is that the algorithm runs in time linear in the the number of vertices and edges of the graph.

Problems That Can Be Solved With a Breadth-First Search

Some of the problems that can be solved using BFS include:

  • Finding the shortest path (in number of edges) from a starting vertex to any other vertex in an un-weighted graph
  • Calculating the diameter of a tree
  • Determining whether a graph is bipartite (equivalent to determining if a graph has a two-coloring)
  • Testing whether a graph is connected
  • Computing a spanning forest of a graph
  • Computing a cycle in a graph, or reporting that no cycle exists

Other Algorithms Based on- or Similar to- Breadth-First Search

Djikstra's single source shortest path algorithm.

Prim's algorithm for determining the Minimum-Spanning-Tree in a graph

is the founder of Donaq, a software development consulting company with a focus on mobility. You can find Mike on Google+ and on LinkedIn.
Design copyright (c) Miky Dinescu