# Breadth First Search (BFS)

**Breadth first search**is an algorithm to visit the nodes of a graph or a tree.

In BFS, we use a queue to track the nodes that we need to visit, and a

*hash table*to track nodes we've visited.Starting at the root node, we add all neighbor nodes to the queue, as long as they have not been visited.

The node is then considered

*processed*, so we don't need to explore that node further.We pop the next node from our queue, and repeat the process until the queue becomes empty, at which point we've explored the entire graph.

## Traverse a graph

Step through the graph below and see how nodes become visited (marked in gray).

## Breadth first search in Python

Given a graph as an

*adjacency list*, here's how we visit its nodes through BFS.Remember, the Python utility

`collections.deque()`

is used to model a *queue*, and a`set`

to model a *hash table*for tracking visited nodes.## 9 Essential Trees & Graphs Coding Interview Problems

Master Trees & Graphs by trying the coding challenges below.

- 1.Inorder TraversalEasy
- 2.Tree SumEasy
- 3.Tree HeightEasy
- 4.LCAMedium
- 5.Max Path SumHard
- 6.Search mazeMedium
- 7.Number of islandsMedium
- 8.Kth SmallestMedium
- 9.Sort K ArraysHard