Move it step by step
- Current vertex
- none
- Current edge
- none
- Visit order
- A
Queue (leaves from the front, joins at the back)
- A
- Checking its neighbors now
- Visited (number is visit order)
- Not yet visited
- Edge being looked at
When a vertex has two or more neighbors, we look at them in name order (A, B, C, ...). A vertex is marked visited at the moment it's enqueued.
Step 1 of 210 edges seen1 visited1 in queue
Mark the start vertex A as visited and enqueue it.
The pseudocode line currently running
- 1Mark the start vertex s as visited and enqueue it
- 2While the queue is not empty, repeat the following
- 3u = dequeue the vertex at the front
- 4Look at each neighbor v of u, in name order
- 5If v is unvisited, mark it visited and enqueue it
- 6If v is already visited, do nothing
Change the example
Try predicting
You're on step 1.
Which vertex comes out of the queue next?
What you'll learn
- The flow of visiting vertices in order of distance from the start vertex
- Why using a queue visits vertices in order of distance, and why you need a visited marker
Prerequisites
- Queues (first in, first out)
- Vertices and edges in a graph
How this traversal works
Breadth-first search (BFS) starts at a vertex and visits every vertex reachable by one edge, then every vertex reachable by two edges, and so on, expanding outward in order of distance.
The vertices to check next wait in a queue. Because the nearer vertices were enqueued first, they come out first, so the traversal naturally proceeds in order of distance. Marking each vertex as visited once means that even in a graph with a cycle, no vertex gets checked twice.
Steps, with an example
- 1Mark the start vertex as visited and enqueue it
- 2Dequeue one vertex from the front of the queue
- 3Look at that vertex's neighbors; mark any unvisited ones as visited and enqueue them at the back
- 4Repeat steps 2 and 3 until the queue is empty
| Dequeued vertex | Newly visited | Queue (from the front) |
|---|---|---|
| A | B, C | B, C |
| B | D, E | C, D, E |
| C | F, G | D, E, F, G |
| D | none | E, F, G |
| E | none | F, G |
| F | none | G |
| G | none | none |
Work done and complexity
| What we count | Count | Complexity |
|---|---|---|
| Dequeuing | Once per vertex | O(V) |
| Looking at edges | Twice per edge (once from each side) | O(E) |
| Combined | Proportional to the number of vertices plus edges | O(V + E) |
V is the number of vertices and E is the number of edges. The tree example has 7 vertices and 6 edges, so we dequeue 7 times and look at 12 edges. Whether a vertex is visited is tracked with a set, so checking it takes one step. If you tracked it with a list and searched it every time, you wouldn't stay within this count. Sorting neighbors into name order is just to make the figure easier to follow, and isn't counted here.
When to use it
Good fit
- When you want the shortest path measured by number of edges (the fewest moves through a maze)
- When you want to count everything reachable from a vertex (the size of a connected component)
- When you want to expand outward from the nearest things first (friends of friends)
Not a good fit
- When edges have different lengths (use Dijkstra's algorithm instead)
- When you want to follow a single path as deep as it goes (use depth-first search instead)
Code
Pseudocode
- 1Mark the start vertex s as visited and enqueue it
- 2While the queue is not empty, repeat the following
- 3u = dequeue the vertex at the front
- 4Look at each neighbor v of u, in name order
- 5If v is unvisited, mark it visited and enqueue it
- 6If v is already visited, do nothing
Working code
▶ Press “Run” to see the result here
Edit the Python or JavaScript and press “Run” to see the result right away. Java is read-only here.
FAQ
- Why mark a vertex visited when it's enqueued, instead of when it's dequeued?
- If you marked it visited only when it's dequeued, another vertex could discover the same vertex before the mark is set, and you'd enqueue it twice. Marking it when it's enqueued guarantees every vertex is queued only once.
- What happens if you replace the queue with a stack?
- Then the most recently added vertex comes out first, so the traversal follows a single path as deep as it goes. That's the shape of depth-first search, and it no longer visits vertices in order of distance.
- What if I want to visit disconnected vertices too?
- Go through every vertex in order, and whenever you find one that isn't visited yet, start a fresh BFS from there. The number of times you restart is the number of connected components.
