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

## Comments

So empty here ... leave a comment!