Facebook

Breadth First Search in Graphs

Breadth First Search is a technique to visit all the nodes of graph in a well-defined way.This technique can be applied  to  directed,undirected,weighted or unweighted  graph.Queues are used as a data structure to store elements.

  • BFS traverses all the nodes and edges of graph.
  • BFS in graph with m vertices and n edges takes O(n+m) time.

Example

Say we have a graph as shown in  Fig 1

Screen Shot 2014-07-15 at 5.09.35 PM
Fig 1 : A Graph

 

  • Start from any vertex say A.(Fig 2)
  • Visit and mark A.
  • Look for neighbors of A.
  • Result list --> A
  • Find all the vertices connected to A.E,B,D are connected to A .
  • Pick any random neighbor of A.Say B.
Screen Shot 2014-07-16 at 1.26.21 PM
Fig 2 : Mark A
1
Fig 2 : Mark B

 

  • Visit B and mark it.(Fig 2)
  • Add B to the queue.
  • Result --> AB
  • Look for next vertex which is connected to A.
  • Say  D is chosen.
  • Result -->ABD
  • Visit D and mark it.(Fig 3)
  • Add D to the queue.
Screen Shot 2014-07-15 at 5.27.56 PM
Fig 3 : Mark D
  • Look for any another vertex connected  to A.
  • E is connected to A.(Fig 4)
  • Visit E and mark it.
  • Result -->ABDE
  • Add E to the queue.
  • Screen Shot 2014-07-15 at 5.30.31 PM
    Fig 4 : Mark E
  • Look for any other vertex connected to A.
  • No other vertex is connected to A.
  • Now,dequeue B.
  • Screen Shot 2014-07-15 at 5.35.13 PM
  •  Find neighbor vertices  connected to B.
  • Visit C and mark it.(Fig 5)
  • Result --> ABDEC
  • Add C to the queue.
Screen Shot 2014-07-15 at 5.39.08 PM
Fig 5 : Mark C
  • Look for next unvisited element connected to B.
  • No other unvisited element is connected to B.
  • Dequeue D.
  • Screen Shot 2014-07-15 at 5.42.49 PM
  • Look for another unvisited vertices connected to D.
  • No other unvisited vertex is connected to D.
  • Dequeue E.
  • Screen Shot 2014-07-15 at 5.44.40 PM
  • Look for unvisited neighbors of E.
  • Visit F and mark it.(Fig 6)
  • Result --> ABDECF
  • Add F to the queue.
Screen Shot 2014-07-15 at 6.07.19 PM
Fig 6 : Mark F

 

  • Look for another vertex connected to E.
  • G is connected to E.
  • Visit G and mark it.(Fig 7)
  • Result --> ABDECFG
  • Add G to the queue.
Screen Shot 2014-07-15 at 6.08.57 PM
Fig 8 : Mark G

 

  • There are no unvisited neighbors of C,F, and G.
  • Dequeue C,F and G one by one.
Rate this post

Comments

So empty here ... leave a comment!

Leave a Reply

Your email address will not be published. Required fields are marked *

Sidebar