### Breadth first traversal

The algorithm can be understood as a

*"fire spreading"*on the graph, at the 0th step only the source is on fire. At each step, the buring fire at each vertex spreads to all its neighbors.

The

*ring of fire*is expanded at each iteration. We use a

**data structure.**

*queue*Algorithm

1. Add root node to the queue, and mark it as visited(already explored).

2. Loop through the queue as long as it's not empty do the following.

1. Get and remove the node at the top of the queue(current).

2. For every non-visited child of the current node, do the following:

1. Mark it as visited.

2. Check if it's the destination node, If so, then return and terminate.

3. Otherwise, push it to the queue.

3. If queue is empty, then no path exists!

Computational complexity

This algorithm takes**where V is the number of vertices and E is the number of edges.**

*O(V + E)*Applications

- peer to peer networking
- search engine crawlers
- social networking websites
- maps and gps navigation software
- cycle detection in undirected graph
- bipartite graph testing
- spotting connected components

References

bfs