Breadth First Search

Breadth First Search is one of the simplest algorithm used for searching a graph. A source vertex s, breadth-first search traverses all the edges of the graph and discovers every vertex that is reachable from source s. It computes the smallest distance from the source to all the reachable vertices.  

For any vertex v reachable from s, the simple path
in the breadth-first tree from s to v corresponds to a “shortest path” from s to v
in G, that is, a path containing the smallest number of edges.

The algorithm works both on directed as well as on un-directed graph.

 

ALGORITHM

BFS(v)   //The graph ‘G’ and array visited[] are global; visited[] is initialized to 0

{

   u =v;

   visited[v]=1;

   repeat

{

  For all vertices w adjacent to u do

   {

    If(visited[w]==0)

    {

      Add w to q;

      visited[w]=1;

     }

  If q is empty then return;

  Delete the rest element u, from q;

  }

}

Source: Google

 

 

TIME COMPLEXITY

After initialization the algorithm ensures each vertex enqueued and dequeued at most once. This operation of enqueueing and dequeueing takes 0(1) times. So total time devoted to v vertices is O(v). The total time spent on scanning adjacency list is O(e). Since the sum of the lengths of all adjacency list is O(e). The overhead for initialization is O(v) and thus total time running DFS is O(v+e).

 

 

 

Contributor's Info

Created:
0Comment