> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook-fall-2026/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook-fall-2026/21.-graph-traversals-and-implementations/21.1-bfs-and-dfs.md).
# 21.1 BFS & DFS
In [Chapter 20.4](/cs61b-textbook-fall-2026/20.-tree-traversals-and-graphs/20.4-graph-problems.md), we developed DFS (Depth First Search) Traversal for graphs. In DFS, we visit down the entire lineage of our first child before we even begin to look at our second child - we literally search ***depth first***.
Here, we will talk about BFS (Breadth First Search) (also known as Level Order Traversal). In BFS, we visit all of our immediate children before continuing on to any of our grandchildren. In other words, we visit all nodes 1 edges from our source. Then, all nodes 2 edges from our source, etc.
The pseudocode for BFS is as follows:
```
Initialize the fringe, an empty queue
add the starting vertex to the fringe
mark the starting vertex
while fringe is not empty:
remove vertex v from the fringe
for each neighbor n of vertex v:
if n is not marked:
add n to fringe
mark n
set edgeTo[n] = v
set distTo[n] = distTo[v] + 1
```
A *fringe* is just a term we use for the data structure we are using to store the nodes on the frontier of our traversal's discovery process (the next nodes it is waiting to look at). For BFS, we use a queue for our fringe.
`edgeTo[...]` is a map that helps us track how we got to node `n`; we got to it by following the edge from `v` to to `n`.
`distTo[...]` is a map that helps us track how far `n` is from the starting vertex. Assuming that each edge is worth a distance of `1`, then the distance to `n` is just one more than the distance to get to `v`. Why? We can use the way we know how to get to `v`, then pay one more to arrive at `n` via the edge that necessarily exists between `v` and `n` (it must exist since in the `for` loop header, `n` is defined as a neighbor of `v`).
This [slide deck](https://docs.google.com/presentation/d/1JoYCelH4YE6IkSMq_LfTJMzJ00WxDj7rEa49gYmAtc4/edit#slide=id.g76e0dad85_2_380) illustrates how this pseudocode can be carried out on an example graph.
#### DFS vs BFS
Question 18.1: What graph traversal algorithm uses a stack rather than a queue for its fringe?
**Answer 18.1**: DFS traversal.
Note however that DFS and BFS differ in more than just their fringe data structure. They differ in the order of marking nodes. For DFS we mark nodes only once we visit a node - aka pop it from the fringe. As a result, it's possible to have multiple instances of the same node on the stack at a time if that node has been queued but not visited yet. With BFS we mark nodes as soon as we add them to the fringe so this is not possible.
Recursive DFS implements this naturally via the recursive stack frames; iterative DFS implements it manually:
```
Initialize the fringe, an empty stack
push the starting vertex on the fringe
while fringe is not empty:
pop a vertex off the fringe
if vertex is not marked:
mark the vertex
visit vertex
for each neighbor of vertex:
if neighbor not marked:
push neighbor to fringe
```
\\
---
# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.
## 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, and the optional `goal` query parameter:
```
GET https://cs61b-2.gitbook.io/cs61b-textbook-fall-2026/21.-graph-traversals-and-implementations/21.1-bfs-and-dfs.md?ask=&goal=
```
`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.
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.