> For the complete documentation index, see [llms.txt](https://cs61b.bencuan.me/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b.bencuan.me/algorithms/searching/breadth-first-search-bfs.md).

# Breadth First Search (BFS)

Breadth First Search (BFS), like [Depth First Search (DFS)](/algorithms/searching/depth-first-search-dfs.md), 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.**

![](/files/-M7A0MRdy5PIS1OswbG9)

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](/algorithms/shortest-paths/dijkstras-algorithm.md)).

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

![](/files/-M7A2TdiOb0Wsz8KXWfA)

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

![](/files/-M7A2gaPKUdu3Bersd6m)

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

![](/files/-M7A2x8HIBKp9OIdPe9A)

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.

![](/files/-M7A36Etxx4Ragwidywn)

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.