Using a queue
- Algorithms course
- Intermediate
- Lesson 54/80
- 4 min
BFS uses a queue.
Using a queue
At the heart of BFS lies a queue. Newly discovered vertices go to the back; the next vertex is taken from the front.
This FIFO order ensures vertices are processed by distance order; smaller distance first.
When the queue empties, BFS is complete; no vertex remains to discover.
The frontier
The queue is called the frontier: it holds vertices waiting to expand into the next layer.
The frontier holds discovered but unprocessed vertices; this distinction is core to BFS.
When the frontier empties, all reachable vertices are processed; the search ends.
Practice Queue size trace
Write bfs_queue_max(graph, start). Return the maximum queue size during BFS. Print 2 with print(bfs_queue_max({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)).
Starter code
def bfs_queue_max(graph, start):
# Max queue sizeSample solution
def bfs_queue_max(graph, start):
# Max queue size
visited = set()
queue = [start]
max_size = 1
while queue:
node = queue.pop(0)
if node not in visited:
visited.add(node)
for nb in graph[node]:
if nb not in visited:
queue.append(nb)
if len(queue) > max_size:
max_size = len(queue)
return max_size
print(bfs_queue_max({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0))Expected output
2
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Queue operation
node = queue.____node = queue.pop(0)Explanation: pop(0) is right.
2 Using a queue: match the terms
| Term | Meaning |
|---|---|
frontier |
Pending vertices |
pop(0) |
Take front |
append |
Add back |
FIFO |
Order rule |
3 Where is a newly discovered vertex added in BFS?
- Back of the queue Correct answer
- Onto the stack
- Front of the queue
- Heap root
Explanation: Back of the queue.