# Breadth First Search (BFS)

Breadth First Search (BFS), like [Depth First Search (DFS)](https://cs61b.bencuan.me/algorithms/searching/depth-first-search-dfs), is a method of **traversing a graph.** BFS simply traverses in a different order, but otherwise is very similar to DFS. 

The main difference is that BFS **visits all children before any subgraphs.** In a tree, we call this **level order.**

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M79zpM9iWpZnGXBsP9S%2F-M7A0MRdy5PIS1OswbG9%2Fimage.png?alt=media\&token=f442076f-6a66-4372-9381-4d9f8ac07f53)

For the example tree above, a level order traversal would go in this order: **D B F A C E G.** 

## Step by Step

**Let's see how we might implement BFS.** 

Some data structures we will need are:

* A graph to traverse.
* A queue **Q** to keep track of which nodes need to be processed next.
* A list of booleans **marked** to keep track of which nodes were already visited.
* (Optional) **edgeTo** and **distTo** to keep track of information that might be useful for other applications (like [Dijkstra's Algorithm](https://cs61b.bencuan.me/algorithms/shortest-paths/dijkstras-algorithm)).

First, let's start with a vertex in the graph by marking it and adding it to the queue.

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M79zpM9iWpZnGXBsP9S%2F-M7A2TdiOb0Wsz8KXWfA%2Fimage.png?alt=media\&token=170b4917-251e-4d7b-a6d5-2241b921e692)

The next step is to **remove A from the queue** and **add its children** (B and C) **to the queue.** Also, we need to **mark all of the children.**

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M79zpM9iWpZnGXBsP9S%2F-M7A2gaPKUdu3Bersd6m%2Fimage.png?alt=media\&token=830b02d4-692c-4ca6-a26d-324c281eb050)

Next, we'll move onto the **next item on the queue** (B). We'll do the same thing that we did with A: remove B, mark all its children, and add its children to the queue. **Since C is already marked, we do not add it to the queue again.**

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M79zpM9iWpZnGXBsP9S%2F-M7A2x8HIBKp9OIdPe9A%2Fimage.png?alt=media\&token=a57d3c95-6213-40a0-85bd-7336c0dbedc8)

Now, we'll move on to the next item on the queue, C, and do the same thing. Again, we won't add C or A because they are both marked.

![](https://628945320-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M6l_SlXhV46y96GQwmG%2F-M79zpM9iWpZnGXBsP9S%2F-M7A36Etxx4Ragwidywn%2Fimage.png?alt=media\&token=c3695a0f-829e-445e-89bf-eb50324f9fb8)

Finally, we'll visit the two remaining nodes in the queue, D and E. Since all of the nodes are marked now, there aren't any other nodes to visit.