Home » Graphs(We Run Facebook) » Breadth-First Search

Breadth-First Search

Overall Strategy of BFS Algorithm

Breadth-first search starts at a given vertex s, which is at level 0. In the first stage, we visit all the vertices that are at the distance of one edge away. When we visit there, we paint as “visited,” the vertices adjacent to the start vertex s – these vertices are placed into level 1. In the second stage, we visit all the new vertices we can reach at the distance of two edges away from the source vertex s. These new vertices, which are adjacent to level 1 vertices and not previously assigned to a level, are placed into level 2, and so on. The BFS traversal terminates when every vertex has been visited.

To keep track of progress, breadth-first-search colors each vertex. Each vertex of the graph is in one of three states:

1. Undiscovered;
2. Discovered but not fully explored; and
3. Fully explored.

The state of a vertex, u, is stored in a color variable as follows:

1. color[u] = White – for the “undiscovered” state,
2. color [u] = Gray – for the “discovered but not fully explored” state, and
3. color [u] = Black – for the “fully explored” state.

a. After initialization (paint every vertex white, set d[u] to infinity for each vertex u,  and set the parent of every vertex to be NIL), the source vertex is discovered in line 5. Lines 8-9 initialize Q to contain just the source vertex s.

b. The algorithm discovers all vertices 1 edge from s i.e., discovered all vertices (w and r) at level 1.

c.

d. The algorithm discovers all vertices 2 edges from s i.e., discovered all vertices (tx, and v) at level 2.

e.

f.

g. The algorithm discovers all vertices 3 edges from s i.e., discovered all vertices (u and y) at level 3.

h.

i. The algorithm terminates when every vertex has been fully explored.

 

Analysis

  • The while-loop in breadth-first search is executed at most |V| times. The reason is that every vertex enqueued at most once. So, we have O(V).
  • The for-loop inside the while-loop is executed at most |E| times if G is a directed graph or 2|E| times if G is undirected. The reason is that every vertex dequeued at most once and we examine (uv) only when u is dequeued. Therefore, every edge examined at most once if directed, at most twice if undirected. So, we have O(E).

Therefore, the total running time for breadth-first search traversal is O(V + E).


/** Checks if the specified value exists in the binary tree */

public static boolean search( Node node, int value ) {

 // Check if it's an empty tree.
 if( node == null ) {
 return false;
 }

 Queue<Node> queue = new LinkedList<Node>( );
 queue.offer( node );

 while( ! queue.isEmpty( ) ) {

 Node currentNode = queue.poll( ); //
 System.out.print(" "+currentNode.data); //

 if( currentNode.data == value ) {
 // Found the value!
 return true;
 }

 if( currentNode.left != null ) {
 queue.offer( currentNode.left );// The offer(E e) method is used to insert the specified element
 // into this priority queue.
 }

 if( currentNode.right != null ) {
 queue.offer( currentNode.right );
 }
 }

 // Not found.
 return false;
 }

 


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

%d bloggers like this: