# 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

• 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.

• 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.
• 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.
• Look for any other vertex connected to A.
• No other vertex is connected to A.
• Now,dequeue B.
•  Find neighbor vertices  connected to B.
• Visit C and mark it.(Fig 5)
• Result --> ABDEC
• Add C to the queue.
• Look for next unvisited element connected to B.
• No other unvisited element is connected to B.
• Dequeue D.
• Look for another unvisited vertices connected to D.
• No other unvisited vertex is connected to D.
• Dequeue E.
• Look for unvisited neighbors of E.
• Visit F and mark it.(Fig 6)
• Result --> ABDECF
• Add F to the queue.

• 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.

• There are no unvisited neighbors of C,F, and G.
• Dequeue C,F and G one by one.
2 (40%) 1 vote