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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cs61b.bencuan.me/algorithms/searching/breadth-first-search-bfs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.