Difference between BFS and DFS

Breadth First Search and Depth First Search

 

Property

Breadth First Search

Depth First Search
Also called BFS DFS
Tree produced Breadth-first tree Depth-first tree
Algorithm type It is a graph search algorithm It is a graph search algorithm
Applies for both directed/undirected graph? It is for both directed and undirected graph It is for both directed and undirected graph
Data structure The data structure used is Queue The data structure used is Stack
Psuedo code

 

 
     
     
     
     

 

Contributor's Info

Created:
0Comment
Breadth First Search(1)

Breadth First Search

 

The idea is to visit of the vertices at distance 'k' from the current vertex before visiting the vertices at distance 'k+1' 

Explanation

 

Applying BFS is a very simple algorithm, Just follow the below steps of the flowchart.

Before starting the algorithm, Remember these terms:

 

1) Life is white sheet of paper : so a white vertex in graph means the vertex has not been visited yet

2) Once you start writing your life with a pencil, it will turn gray : so a gray vertex in graph means the vertex is being visited

3) Finally, you die and your ashes turn black : so a black vertex in graph means the vertex has been visited

 

Flowchart

 

Let us have the below graph in the left, and an empty queue Q in the right

Now, use the flowchart and keep matching your steps with my steps:

 

Choose any vertex as your starting point of algorithm, let us choose vertex s. Color all vertices as white except vertex s, color vertex s as gray.

 

Fig 1:

Enqueue vertex s.

Fig 2: 

Q is empty?

No.

dequeue(Q)

prints s

 

choose a neighbour of s

let us choose w

w is white?

Yes.

color w as gray

Fig 3: 

Enqueue(w)

Fig 4: 

 

choose a neighbour of s

let us choose r

r is white?

Yes.

color r as gray

Fig 5:

Enqueue(r)

Fig 6:

 

choose a neighbour of s

But.....see, now we don't have any white neighbour of s

so s is completed now.

color s as black

Fig 7:

Q is empty?

No.

dequeue(Q)

prints w

Fig 8: 

choose a neighbour of w

let us choose t

t is white?

Yes.

color t as gray

Fig 9:

Enqueue(t)

Fig 10: 

choose a neighbour of w

let us choose x

x is white?

Yes.

color x as gray

Fig 11: 

Enqueue(x)

Fig 12: 

 

choose a neighbour of w

But.....see, now we don't have any white neighbour of w

so w is completed now.

color w as black

Fig 13: 

Q is empty?

No.

dequeue(Q)

prints r

Fig 14: 

choose a neighbour of r

let us choose v

v is white?

Yes.

color v as gray

Fig 15: 

Enqueue(v)

Fig 16: 

choose a neighbour of r

But.....see, now we don't have any white neighbour of r

so r is completed now.

color r as black

Fig 17: 

Q is empty?

No.

dequeue(Q)

prints t

Fig 18: 

choose a neighbour of t

let us choose u

u is white?

Yes.

color u as gray

Fig 19: 

choose a neighbour of t

But.....see, now we don't have any white neighbour of t

so t is completed now.

color t as black

Fig 20: 

Q is empty?

No.

dequeue(Q)

prints x

Fig 21: 

choose a neighbour of x

let us choose y

y is white?

Yes.

color y as gray

Fig 21: 

Psuedocode

 

BFS(G,s)

{

 

for each vertex v in G except s:

{

      v.color=white;

}

 

s.color=gray;

 

enqueue(Q,s);

 

while(Q is not empty)

{

      u=Dequeue(Q);

      print(u);

            

            for(all neighbours v of u)

            {

                        if(v.color==white)

                        {

                                    v.color=gray;

                                    Enqueue(Q,v);

                         }

                       

                        u.color=black;

            }

}

 

}

 

Time complexity

 

BFS has a time complexity of O(V+E) if we have graph stored in an adjacency list, and O(V2) if we have graph stored in an adjacency matrix.

Contributor's Info

Created:
0Comment
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